Finite state machines

The formula

An FSM is not a single equation; it is a tuple that pins down every part of the machine. Two flavors, one idea.

Moore machine:  M = (S, s0, Σ, Λ, δ, G)
    S   finite set of states
    s0  the start state, s0 ∈ S
    Σ   input alphabet (the events you can feed it)
    Λ   output alphabet (what it can emit)
    δ   transition function   δ: S × Σ → S      (state, input) → next state
    G   output function       G: S → Λ           output depends on STATE only

Reading: where you go next is a function of where you are and what just came in; what you output is a function only of where you are.

Mealy machine:  M = (S, s0, Σ, Λ, T, G)
    T   transition function   T: S × Σ → S      same as above
    G   output function       G: S × Σ → Λ       output depends on STATE and INPUT

Reading: same transition rule, but output is a function of the state and the current input together — so a Mealy machine can react within the same step, before the state actually changes.

Deterministic finite automaton (the acceptor form):
    DFA = (S, s0, Σ, δ, F),   F ⊆ S is the set of accepting states

Reading: strip the output alphabet and mark some states "accept." Feed a string; if you land in an accepting state, the string is in the language. This is the recognizer version — pattern matching in hardware form.

Product (parallel composition) of two machines A and B:
    |S_A×B| = |S_A| · |S_B|

Reading: run two machines side by side and the combined state count is the product, not the sum. That multiplication is the whole reason big FSMs get out of hand.

Where you meet it

Embedded firmware review board. A junior brings a motor controller with a while(1) loop full of nested if flags: is_homing, fault_latched, estop, moving. Six booleans is 2⁶ = 64 implicit states, most of them nonsense combinations nobody reasoned about. The reviewer's job is to make the machine explicit: name the legal states, draw the transitions, and delete the impossible ones. The flag soup becomes an enum and a switch.
Protocol handler on the bench. Parsing a serial or Ethernet frame — preamble, header, payload, CRC — is a textbook DFA. You are in WAIT_SYNC until the sync byte arrives, then READ_LEN, then READ_PAYLOAD counting down bytes, then CHECK_CRC. Each received byte is an input symbol that drives one transition. When the link glitches, you debug by asking "what state was the parser in when it choked."
Automated test sequencer. A test stand walks a UUT through IDLE → PRECHARGE → APPLY_LOAD → SETTLE → MEASURE → SAFE. Each step has entry conditions, a timeout, and abort paths back to SAFE. Writing the sequencer as a formal state machine — instead of a script with sleep() calls — is what lets you prove every fault path lands somewhere safe, and what lets the next engineer read the sequence off one diagram.
FPGA / HDL design. Verilog and VHDL synthesize FSMs directly. Here the Moore-vs-Mealy choice is not academic: a Moore output is registered and stable, a Mealy output can combinationally track the input and shave a clock cycle — at the cost of glitches propagating straight through.

How it works

The core discipline is this: at any instant the machine is in exactly one state, and the only thing that can happen is a transition triggered by an input. Everything the system "remembers" is encoded in which state it is in. That is the constraint that makes an FSM analyzable — and the constraint people violate the moment they add a side variable the state diagram doesn't show.

Moore vs. Mealy is a timing tradeoff, not a capability one. The two are equally expressive; anything one can do, the other can do (any regular language). The difference is when the output appears. Moore output is a function of state alone, so it settles after the transition and holds steady — one step of latency, but clean and glitch-free. Mealy output is a function of state and input together, so it can respond in the same step the input arrives, saving a cycle, but it can also chatter if the input is noisy and it can create combinational paths that ripple through chained machines. On a bench, the practical rule: use Moore when you want stable, predictable outputs a scope can trust; use Mealy when you need the fast reaction and you control the input timing.

The mistake people make is hidden state. An FSM is only valid if the finite state set truly captures all the memory. The instant you add a counter, a flag, or a "remember the last thing" variable that isn't part of the declared state, you've built a machine with far more states than your diagram shows — and the ones you didn't draw are exactly the ones that fail in the field. If the parser needs to count 512 payload bytes, that counter is state — fold it in honestly and accept that your real machine has 512 times more states than the diagram shows. It is still an FSM, because the bound is fixed; only when the count is unbounded (arbitrary-length payloads, nested framing) have you left the FSM class for a pushdown or counter automaton.

State explosion is the hard limit. Because parallel machines multiply, a system built from ten independent 4-state subsystems has up to 4¹⁰ ≈ 1.05 million combined states. Flatten everything into one diagram and it is unreadable and untestable. This is the ceiling on the flat-FSM model, and it is real: a modem, an autopilot mode manager, a UI with dozens of concurrent widgets cannot be one flat chart.

Statecharts are the fix for explosion. Hierarchy (a state that contains sub-states, so a shared estop → SAFE transition is drawn once at the parent level instead of on every child) and orthogonality (independent regions running concurrently instead of as a cross-product) collapse the diagram. The same ten subsystems drawn as ten orthogonal regions is ~40 boxes, not a million. That structural saving is the entire point of statecharts, and it is why they, not flat FSMs, are what actually ships in complex reactive systems.

Limits of validity. A finite state machine has, by definition, finite memory — it cannot count without bound, match nested brackets, or parse arithmetic with nesting. Those need a stack (pushdown automaton) or more. If your "state machine" keeps needing new states proportional to input size, you've outgrown the model; that's a feature of the theory, not a bug in your design.

History

The finite-state model grew out of switching theory, not abstract math. In the early 1950s, engineers designing relay and vacuum-tube circuits needed a disciplined way to synthesize logic that depended on past inputs — sequential circuits — rather than eyeballing them. George H. Mealy, working at Bell Labs, published A Method for Synthesizing Sequential Circuits in the Bell System Technical Journal in September 1955, giving a formal procedure and, in the process, defining the machine that now carries his name — one whose output depends on both state and input ^[1]^[2]. Mealy's own paper credits the earlier switching-theory work of D. A. Huffman and E. F. Moore that he built on ^[1].

A year later, Edward F. Moore, also at Bell Labs, published Gedanken-experiments on Sequential Machines (1956), which treated the machine as an object you could probe with input experiments to learn its structure — and defined the complementary model where output depends on state alone ^[3]^[4]. So within about twelve months the two canonical forms were both on the table, from the same lab, aimed at the same practical problem: how to build and reason about circuits with memory. The names stuck; the two models have been taught as a matched pair ever since.

The next leap came from a different direction. By the 1980s the flat model was drowning in state explosion for real reactive systems — avionics, telecom switches. David Harel published Statecharts: A Visual Formalism for Complex Systems in Science of Computer Programming in 1987, adding hierarchy, concurrency (orthogonal regions), and history to the plain state diagram ^[5]^[6]. Statecharts are what let a state-machine description scale from a lab exercise to a system spec you can actually put in front of a review board, and they underpin the state-machine tooling in UML and in embedded design tools today.

Related tools

/tools/ne555-astable
/tools/ne555-monostable
/tools/adc-resolution

Sources

Written by HE in our own words from the cited sources — engineering judgment included, your stamp still required. All entries →