Editing Finite-state machine (section)

{{short description|Mathematical model of computation}}
{{redirect|State machine|infinite-state machines|Transition system|fault-tolerance methodology|State machine replication}}
{{redirect|SFSM|the Italian railway company|Circumvesuviana}}
{{redirect|Finite automata|the electro-industrial group|Finite Automata (band)}}
{{use dmy dates|date=January 2020|cs1-dates=y}}
{{Automata theory}}

A '''finite-state machine''' ('''FSM''') or '''finite-state automaton''' ('''FSA''', plural: ''automata''), '''finite automaton''', or simply a '''state machine''', is a mathematical [[model of computation]]. It is an [[abstract machine]] that can be in exactly one of a finite number of ''[[State (computer science)|states]]'' at any given time. The FSM can change from one state to another in response to some [[Input (computer science)|inputs]]; the change from one state to another is called a ''transition''.<ref>{{Cite book|title=Formal Methods in Computer Science|last=Wang|first=Jiacun|publisher=CRC Press|year=2019|isbn=978-1-4987-7532-8|pages=34}}</ref> An FSM is defined by a list of its states, its initial state, and the inputs that trigger each transition. Finite-state machines are of two types—[[Deterministic finite automaton|deterministic finite-state machines]] and [[Nondeterministic finite automaton|non-deterministic finite-state machines]].<ref>{{cite web|url=https://brilliant.org/wiki/finite-state-machines/|title=Finite State Machines – Brilliant Math & Science Wiki|website=brilliant.org|access-date=14 April 2018}}</ref> For any non-deterministic finite-state machine, an equivalent deterministic one can be constructed.

The behavior of state machines can be observed in many devices in modern society that perform a predetermined sequence of actions depending on a sequence of events with which they are presented. Simple examples are: [[vending machine]]s, which dispense products when the proper combination of coins is deposited; [[elevator]]s, whose sequence of stops is determined by the floors requested by riders; [[traffic light]]s, which change sequence when cars are waiting; [[combination lock]]s, which require the input of a sequence of numbers in the proper order.

The finite-state machine has less computational power than some other models of computation such as the [[Turing machine]].<ref name="Belzer">{{cite book
 | last1 = Belzer
 | first1 = Jack
 | first2=Albert George |last2=Holzman |first3=Allen |last3=Kent
 | title = Encyclopedia of Computer Science and Technology |volume=25
 | publisher = CRC Press
 | year = 1975
 | location = USA
 | pages = 73
 | url = https://books.google.com/books?id=W2YLBIdeLIEC
 | isbn = 978-0-8247-2275-3}}</ref> The computational power distinction means there are computational tasks that a Turing machine can do but an FSM cannot. This is because an FSM's [[Computer memory|memory]] is limited by the number of states it has. A finite-state machine has the same computational power as a Turing machine that is restricted such that its head may only perform "read" operations, and always has to move from left to right. FSMs are studied in the more general field of [[automata theory]].