FSMs

Finite state machines (FSMs) are mathematical models of computation used to design both software and hardware that exhibit a finite number of modes or states. An FSM consists of a finite set of states, an input alphabet, a transition function that maps a state and an input symbol to a next state, a designated start state, and, for many definitions, a set of accepting (or final) states. In some contexts an FSM also produces output, leading to two common variants known as Mealy and Moore machines.

Deterministic finite automata (DFAs) have exactly one next state for every combination of current state and input symbol; nondeterministic finite automata (NFAs) may have multiple possible next states and may include epsilon transitions that consume no input. Both DFAs and NFAs recognize the same class of languages, the regular languages; NFAs can be converted to equivalent DFAs via subset construction, and DFAs can be minimized to reduce the number of states.

Mealy and Moore machines are FSMs with output. In a Mealy machine the output depends on the current state and input; in a Moore machine the output depends only on the current state.

Formal definitions describe an FSM as a 5-tuple. For a DFA, M = (S, Σ, δ, s0, F) where S is a finite set of states, Σ is the input alphabet, δ: S×Σ→S is the transition function, s0∈S is the start state, and F⊆S is the set of accepting states. For NFAs δ maps to sets of states.

Applications include lexical analysis, protocol design, control systems, hardware design and simple user interfaces. Limitations include limited memory; they cannot recognize patterns requiring unbounded memory, such as non-regular languages. They are often used with regular expressions and can be implemented efficiently in software and hardware.