# finite state machine

(definition)

**Definition:**
A *model of computation* consisting of a set of *states*, a *start state*, an input *alphabet*, and a *transition function* that maps input symbols and current states to a *next state*. Computation begins in the start state with an input string. It changes to new states depending on the transition function. There are many variants, for instance, machines having actions (outputs) associated with transitions (*Mealy machine*) or states (*Moore machine*), multiple start states, transitions conditioned on no input symbol (a null) or more than one transition for a given symbol and state (*nondeterministic finite state machine*), one or more states designated as *accepting states* (*recognizer*), etc.

**Also known as** finite state automaton.

**Generalization** (I am a kind of ...)

*model of computation*, *Turing machine*, *state machine*.

**Specialization** (... is a kind of me.)

*deterministic finite state machine*, *nondeterministic finite state machine*, *Kripke structure*, *finite state transducer*, *Markov chain*, *hidden Markov model*, *Mealy machine*, *Moore machine*.

*Note:
Equivalent to a restricted **Turing machine* where the head is read-only and shifts only from left to right. After Algorithms and Theory of Computation Handbook, page 24-19, Copyright © 1999 by CRC Press LLC. Appearing in the Dictionary of Computer Science, Engineering and Technology, Copyright © 2000 CRC Press LLC.

Author: PEB

## Implementation

Jan Daciuk's Finite state utilities (C++) including many links to other code, papers, etc. David Lutterkort's Finite Automata library - libfa (C), which is part of Augeas, supports many operations like "compile" a regular expression into a finite automaton, minimize, union, intersect, and minus. Finite State Automata Utilities (Prolog), which generate C code, minimize, visualize, etc. Page has binaries, too. For regular expressions generate NFSM, make deterministic, and optimize (Haskell). Oleg Kiselyov's program to minimize a finite state machine (Prolog).
## More information

The FASTAR (Finite Automata Systems - Theoretical and Applied Research) group site links to some papers, conferences, and projects.

Go to the
Dictionary of Algorithms and Data
Structures home page.

If you have suggestions, corrections, or comments, please get in touch
with
Paul E. Black.

Entry modified 12 May 2008.

HTML page formatted Tue Dec 6 16:16:32 2011.

Cite this as:

Paul E. Black, "finite state machine", in
*Dictionary of Algorithms and Data
Structures* [online], Paul E. Black, ed.,
U.S. National Institute of
Standards and Technology. 12 May 2008. (accessed TODAY)
Available from: http://www.nist.gov/dads/HTML/finiteStateMachine.html