A finite state machine (FSM) is a model of computation that can only be in one “state” at a time, and changes between states based on specific inputs. Think of a turnstile at a subway station: it’s either locked or unlocked. Insert a coin, and it transitions from locked to unlocked. Push through, and it goes back to locked. That turnstile has two states, two inputs, and clear rules for switching between them. Every finite state machine, no matter how complex, follows that same basic logic.
FSMs show up everywhere, from the circuits inside your computer to the behavior of enemies in video games to the way compilers process code. Understanding them gives you a surprisingly useful mental model for thinking about systems that respond to input over time.
The Five Core Components
Formally, a finite state machine is defined by five things:
- States: A finite set of conditions the machine can be in. The turnstile has two (locked, unlocked). A traffic light has three (red, yellow, green). The number can be large, but it’s always limited.
- Alphabet: The set of possible inputs the machine can receive. For the turnstile, that’s “coin” and “push.”
- Transition function: The rules that determine which state the machine moves to, given its current state and the input it receives. This is the heart of the machine.
- Start state: The state the machine begins in.
- Accept states: One or more states that count as a “success” or valid ending point, if the machine is being used to recognize patterns.
You can represent an FSM visually with a state diagram: circles for states, arrows for transitions, and labels on the arrows showing which input triggers each transition. You can also lay it out as a table, with rows for each current state and columns for each possible input, where each cell tells you the next state. For small machines, diagrams are intuitive. For larger ones, tables become easier to manage.
Deterministic vs. Non-Deterministic
The most common distinction is between deterministic and non-deterministic finite automata (DFA and NFA). In a deterministic machine, every state has exactly one transition for each possible input. There’s never any ambiguity about what happens next. Feed it the same sequence of inputs, and it always follows the same path.
A non-deterministic machine relaxes that rule. A single state can have multiple transitions for the same input, meaning the machine could theoretically follow several paths at once. It can also make “epsilon transitions,” jumping to a new state without consuming any input at all. This sounds more powerful, but here’s the key insight: NFAs and DFAs are mathematically equivalent. Anything an NFA can recognize, a DFA can too. The tradeoff is size. Converting an NFA to a DFA can cause an exponential blowup in the number of states. An NFA with 10 states might need a DFA with over 1,000 states to do the same job.
In practice, this matters for pattern matching engines. NFAs are favored on architectures that can exploit parallelism, since they naturally process multiple possible paths simultaneously. DFAs are faster for straightforward, single-threaded processing because there’s never a choice to resolve.
Mealy and Moore: Two Output Models
The basic FSM definition above is designed to accept or reject input strings. But many real-world applications need the machine to produce output, not just say yes or no. Two classic models handle this differently.
A Moore machine ties its output to the current state alone. If you’re in state A, you always get the same output, regardless of what input just arrived. A Mealy machine ties its output to both the current state and the current input. This makes Mealy machines more responsive (they can react to input within the same cycle), but Moore machines are simpler to reason about since each state has a single, predictable output. Both models are equally powerful in what they can compute; the difference is a design choice about where you want complexity to live.
How FSMs Work in Hardware
In digital electronics, sequential circuits (circuits whose output depends on the history of inputs, not just the current ones) are essentially finite state machines built from physical components. The standard design has three parts: memory elements called flip-flops that store the current state, state logic that combines the current state with inputs to determine the next state, and output logic that generates the appropriate output signals.
A synchronous sequential circuit updates its state on each tick of a clock signal. Between ticks, the combinational logic settles on the next state values, and when the clock ticks, the flip-flops capture those values simultaneously. This is the backbone of control units in processors, communication protocols, and countless embedded systems. When an engineer designs a vending machine controller or an elevator system, they’re typically drawing out an FSM and then translating it into logic gates and flip-flops.
How FSMs Work in Software
Software developers implement finite state machines all the time, even when they don’t call them that. The simplest approach is a switch statement: a variable tracks the current state, and a switch block routes execution based on that state and the incoming input. This works well when the number of states is small.
For larger machines, a table-driven approach is cleaner. You define a two-dimensional array where rows represent states and columns represent possible inputs. Each cell contains the next state (and possibly an action to perform). The runtime code becomes a simple loop: look up the current state and input in the table, update the state, perform the action. This keeps the logic separate from the control flow, making it easier to modify. For very large systems with sparse transitions (most state-input combinations don’t apply), a graph structure is more memory-efficient than a full table.
Common Real-World Uses
Game developers use FSMs heavily for non-player character (NPC) behavior. An enemy in a platformer might have states like wandering, attacking, and fleeing. When the player gets close, the NPC transitions from wandering to attacking. When its health drops low, it transitions to fleeing. Each state defines a different set of behaviors and animations, and the transitions create the illusion of intelligent decision-making from a relatively simple structure.
Regular expressions, the pattern-matching syntax used across programming languages, are directly equivalent to finite automata. Every regular expression can be converted into an FSM that accepts exactly the strings the expression describes, and every FSM can be converted back into a regular expression. When you run a regex search, the engine is typically constructing and executing a finite automaton behind the scenes.
Other common applications include lexical analysis in compilers (breaking source code into tokens), network protocol design (tracking connection states like “listening,” “established,” and “closed”), user interface workflows (managing which screens and interactions are valid at any point), and text parsing.
What Finite State Machines Cannot Do
The word “finite” in the name is the key limitation. An FSM has a fixed amount of memory encoded in its states. It can count up to some predetermined number, but it cannot count without limit. This places FSMs at the bottom of the Chomsky hierarchy, a framework that classifies languages by their computational complexity into four levels: regular, context-free, context-sensitive, and computably enumerable.
Finite automata recognize only regular languages, the simplest class. They fail at tasks that require matching unlimited nested structures. A classic example: an FSM cannot reliably match opening and closing parentheses to arbitrary depth. It can handle three levels of nesting, or thirty, if you build enough states, but there will always be a depth that exceeds its capacity. To handle unlimited nesting, you need a pushdown automaton, which adds a stack (essentially infinite scratch memory) on top of a finite state machine. This is why programming language parsers use context-free grammars rather than regular expressions for syntax analysis.
Natural language has similar properties. Noam Chomsky pointed out in the 1950s that English allows center-embedded constructions (sentences nested inside sentences) to a depth that no finite state machine can fully capture. This insight helped establish that human language requires more computational power than regular grammars can provide.
Despite these limitations, FSMs remain one of the most widely used computational models precisely because they’re simple, predictable, and efficient. Most real-world control problems don’t require infinite memory, and for those problems, a finite state machine is often the cleanest solution available.