FiniteState

Finite-state machines (FSMs), also called finite automata, are computational models with a finite number of states. At any moment, the current state encodes the history of inputs in a compact form, and the next state is determined by the present state and the input symbol.

An FSM is defined by a finite set of states, a finite alphabet of input symbols, a transition function that maps each state and input to a next state, a designated start state, and, for automata, a set of accepting (final) states. In a deterministic finite automaton (DFA) each state-input pair has exactly one next state; in a nondeterministic finite automaton (NFA) a state may have multiple possible next states and epsilon-transitions may occur.

Finite-state machines come in several flavors, including Mealy and Moore machines, which are finite-state transducers that produce outputs. In a Mealy machine outputs depend on the state and input; in a Moore machine outputs depend only on the state.

FSMs are used to model and implement sequential logic and a wide range of computing tasks, such as lexical analysis, protocol parsing, and the control of embedded systems. In formal language theory, they recognize regular languages, and every regular language can be described by a finite automaton or a regular expression. There are systematic methods to convert nondeterministic designs to equivalent deterministic ones and to minimize the number of states in a DFA by merging equivalent states.

Limitations include the inability to recognize non-regular languages, such as those requiring unbounded counting or nested structures. Finite-state models are most effective for systems with bounded memory and simple, regular patterns.