State Machines

A finite state machine (FSM) is a computational model consisting of a finite set of states, an alphabet of input symbols, a transition function mapping (state, symbol) pairs to a next state, a designated start state, and a set of accepting states. At any moment the machine is in exactly one state; it reads input symbols one at a time and transitions accordingly. FSMs recognize exactly the regular languages — the same class described by regular expressions — and are the foundation of lexers, network protocol parsers, UI interaction models, and embedded control systems. Their power lies in their simplicity: an FSM has no memory beyond its current state, making it easy to reason about, implement, and verify.

Key Concepts

Deterministic vs. Nondeterministic (DFA vs. NFA) — A DFA has exactly one transition for each (state, symbol) pair; an NFA may have zero, one, or many, including ε-transitions (transitions on no input). NFAs are easier to construct from regular expressions but harder to execute directly. The subset construction algorithm converts any NFA to an equivalent DFA, potentially exponentially increasing the number of states in the worst case (though this is rare in practice). DFAs execute in O(n) time for input of length n.

State Transition Table — The transition function is often expressed as a 2D table with states as rows and input symbols as columns. This table is the executable artifact: a DFA driver is simply a loop that indexes into the table on each input character. Table-driven lexers (used by lex/flex) compile regular expressions into such tables, yielding compact, fast scanners.

Mealy vs. Moore Machines — Both are finite transducers (FSMs that produce output):

• Moore machine: output depends only on the current state
• Mealy machine: output depends on the current state and the current input symbol

Mealy machines are more compact (fewer states for equivalent behavior) but Moore machines are simpler to reason about because output changes only on state transitions.

Pushdown Automata — Adding a stack to an FSM yields a pushdown automaton (PDA), which recognizes context-free languages — the class of grammars needed to describe nested structures like balanced parentheses or programming language syntax. Recursive descent parsers and LR parsers are implementations of PDAs.

Applications

• Lexers: tokenize source code by recognizing patterns (identifiers, numbers, keywords) as regular languages
• Network protocols: TCP connection states (LISTEN → SYN_RECEIVED → ESTABLISHED → FIN_WAIT → CLOSED) are a classic FSM
• UI state management: XState and similar libraries model component lifecycle as explicit FSMs, eliminating impossible states that arise from ad-hoc boolean flags
• Regex engines: NFA construction from regex, followed by simulation or DFA compilation, is the standard implementation approach
• Embedded control: industrial controllers, traffic lights, vending machines — anywhere an exhaustive enumeration of operating modes is required

State Explosion — As the number of tracked conditions grows, the number of states can grow exponentially (the state explosion problem). Hierarchical state machines (statecharts, as formalized by David Harel) address this by allowing states to contain sub-machines and by supporting parallel (orthogonal) regions, drastically reducing the total state count needed to express complex behavior.

Common Pitfalls

• Leaving transitions undefined for some input symbols — an incomplete FSM is a source of undefined behavior; explicitly add an error/trap state
• Using ad-hoc boolean flags instead of explicit states — this is an implicit, unverifiable FSM that grows unmaintainable
• Conflating statecharts (hierarchical FSMs with entry/exit actions) with flat FSMs — they solve different problem scales

Best Practices

• Draw the state diagram before writing code — visual inspection reveals missing transitions and unreachable states
• Use a state enum rather than string literals to name states — enables exhaustive pattern matching
• For complex UI or protocol logic, prefer a dedicated FSM library (XState for JS/TS, transitions for Python) over hand-coded switch statements

See Also

• Control Flow
• Graph Traversal