Finite-state machine
A finite-state machine models computation with a finite number of states.
Last updated
A mathematical model of computation that can occupy only one of a limited set of states at any moment is called a finite-state machine.[1] When inputs are received, the machine shifts between states, and each such shift is termed a transition.[2] Compared to Turing machines, finite-state machines possess lower computational power.[3]
Quick Facts
- Type
- Mathematical model of computation
- Field
- Theoretical computer science, automata theory
- Variants
- Deterministic and non-deterministic finite-state machines
- Computational power
- Less than a Turing machine; equivalent to a read-only, left-to-right Turing machine
- Common examples
- Vending machines
- elevators
- traffic lights
- combination locks
- turnstiles
Facts from the source article.
Key facts and history
Finite-state machines are classified into deterministic and non-deterministic types, and any non-deterministic machine has an equivalent deterministic one.[4] Finite automata are used in the frontend of programming language compilers for lexical analysis and parsing.[5] Acceptors, classifiers, transducers, and sequencers are categories into which finite-state machines can be divided.[6] Regular languages, for instance the collection of binary strings containing an even count of zeroes, are defined by acceptors.[7]
A Mealy machine's output is determined by both the current state and incoming signals, whereas a Moore machine's output relies solely on the current state.[8]
References
- Wikipedia, "Finite-state machine" (CC BY-SA 4.0), which cites: introduces the alternative terms, finite-state machines and finite automata, at the beginning of Chapter 2. (original not read by us) en.wikipedia.org
- Wikipedia, "Finite-state machine" (CC BY-SA 4.0), which cites: Wang 2019, p. 34 (original not read by us) en.wikipedia.org
- Wikipedia, "Finite-state machine" (CC BY-SA 4.0), which cites: Belzer Holzman Kent 1975, p. 73 (original not read by us) en.wikipedia.org
- Wikipedia, "Finite-state machine" (CC BY-SA 4.0), which cites: Brilliant; Lewis Papadimitriou 1998, p. [https://archive.org/details/elementsoftheory0000lewi_n0x1/page/n10/mode/1up?q=%222+finite+automata%22 Chapter 2: Finite Automata]; Lewis Papadimitriou 1998, p. [https://archive.org/details/elementsoftheory0000lewi_n0x1/page/n10/mode/1up?q=%222+finite+automata%22 Chapter 2: Finite Automata] (original not read by us) en.wikipedia.org
- Wikipedia, "Finite-state machine" (CC BY-SA 4.0), which cites: Aho Sethi Ullman 1986 (original not read by us) en.wikipedia.org
- Wikipedia, "Finite-state machine" (CC BY-SA 4.0), which cites: Keller 2001 (original not read by us) en.wikipedia.org
- Wikipedia, "Finite-state machine" (CC BY-SA 4.0), which cites: Hopcroft Ullman 1979, p. 18 (original not read by us) en.wikipedia.org
- Wikipedia, "Finite-state machine" (CC BY-SA 4.0), which cites: Kaeslin 2008; Schwarz (original not read by us) en.wikipedia.org
Each numbered sentence above was checked against the source it cites before publication. Sentences citing Wikipedia adapt text from the English Wikipedia article Finite-state machine (contributors), used under CC BY-SA 4.0; this entry is available under the same licence. Other sources were used for facts only; no text or images are copied from them.
More in Algorithms And Data Structures
Sources
Compiled from Wikipedia and the sources listed below. Text from Wikipedia is available under CC BY-SA 4.0; this entry is adapted from it.
- Wikipedia: Finite-state machine (CC BY-SA 4.0).
- Word definitions: the , each quoted from its Wikipedia article.
Spotted an error? Know more?
Reader corrections go straight into our review queue. Suggest an edit · How this site is sourced