A finite state machine (FSM) is a mathematical model of computation: a system that’s always in one of a finite number of states, transitions between states based on inputs, and produces outputs as a function of state (and possibly inputs). All sequential circuits are FSMs in the abstract.
An FSM is fully specified by:
- A finite set of states.
- A set of inputs.
- A set of outputs.
- A next-state function mapping (state, input) → next state.
- An output function mapping either state → output (Moore machine) or (state, input) → output (Mealy machine).
- An initial state (the state the machine starts in).
That’s it. Anything that can be described by those five ingredients is an FSM.
Two flavors
The split based on output function:
- Moore: output depends only on the current state.
- Mealy: output depends on the current state and the current input.
The two are equivalent in expressive power — anything one can describe, the other can too — but they trade off state count, output latency, and glitch-freeness. See either note for the comparison.
How to specify an FSM
Three equivalent forms, in order of increasing concreteness:
- State diagram — circles for states, arrows for transitions, labels for inputs/outputs. Best for sketching designs.
- State table — rows for current state, columns for next state and output per input. Best for systematic analysis.
- State equations — Boolean functions for each next-state bit and each output. Best for hardware implementation.
You usually move from 1 → 2 → 3 as you go from spec to circuit. See Sequence detector (FSM design example) for a complete walkthrough.
Hardware structure
Every clocked FSM has the same shape:
- State register ( flip-flops, holding the current state).
- Next-state combinational logic — computes .
- Output combinational logic — computes the output. For Moore, depends only on state; for Mealy, also on input (the cyan path in the diagram).
The clock drives the state register. On each edge, the register loads the next state. The combinational logic settles to its new outputs within the clock period.
Why it matters
FSMs are everywhere in digital design:
- Communication protocols (the receiver’s parser is an FSM).
- Control units (a CPU’s instruction-decode and pipeline-control logic).
- User interfaces (button presses transition between display modes).
- Computer science theory (regular languages are exactly what FSMs can recognize).
Knowing how to specify, analyze, and implement an FSM is the central skill of sequential circuit design.
For optimization (merging equivalent states), see State Reduction. For choosing the binary code per state, see State Assignment.