Finite State Machines

A finite state machine is simply a way to describe what state something is in right now (a traffic light is green, yellow or red) and what makes it switch to another. It's called finite because there's a fixed, limited set of states, and it's always in exactly one of them at a time. That makes it great for computing: one simple description of where things stand is all the machine has to remember. The formula $s_{k+1} = \delta(s_k, x_k)$ looks abstract, but it's just three pieces: $s_k$ (the state right now), $x_k$ (the next input that comes in) and $\delta$ (a lookup table saying which state comes next), and $y_k = \lambda(s_k)$ just reads the output off the current state. It's a fancy way to write a table; bear with the symbols.

Many machines only need to remember a little about the past: a traffic light which color it's showing, a serial receiver which bit comes next, a vending machine how much money has gone in. A finite state machine packages exactly that: a finite set of states, a start state, and a transition function $\delta$ that picks the next state from the current state and the input. Outputs come from the state alone (a Moore machine) or from the state and input together (a Mealy machine, which can react one step sooner).

Example: spot 101 in a bit stream. What does the machine actually need to remember? Only how much of the pattern it has just seen, so that's what the states record:

A common mistake. After a match, it's tempting to send the machine back to $S_0$ to start fresh, since the pattern is "done." It isn't done: from $S_3$, a 0 leaves "10" at the end of the stream, which is exactly $S_2$, and that's how overlapping matches like 10101 get counted twice. The same goes for $S_1$ on another 1: the stream still ends in a "1", so it stays in $S_1$. Always ask what's left over at the end of the stream.

In hardware the state lives in flip-flops, and $N$ states need $\lceil \log_2 N \rceil$ of them with binary encoding. On each clock tick, Boolean next-state logic, built with the tools of the logic unit (K-maps included), computes the next state from the current state bits and the input. FPGA tools often use one-hot encoding instead, one flip-flop per state, because the logic gets simpler.

In firmware it's a switch inside a loop or an interrupt handler:

enum { S0, S1, S2, S3 } s = S0;

void on_bit(int b) {                 // called for each received bit
    switch (s) {
    case S0: s = b ? S1 : S0; break;
    case S1: s = b ? S1 : S2; break;
    case S2: s = b ? S3 : S0; break;
    case S3: s = b ? S1 : S2; break;
    }
    if (s == S3) pattern_found();
}

A state diagram is a directed graph, the next unit's subject, with one arrow per state and input. There's an animation further down that runs the 101 detector on its diagram. What a finite state machine can't do is count without limit. A machine with $N$ states that reads $N + 1$ open parentheses must revisit some state (the pigeonhole principle), so it can't tell those two counts apart, and it can't check that the closing parentheses match. That needs memory that grows, like a stack.

Every protocol controller on a chip (UART, I²C, USB, Ethernet) is a finite state machine, and so is the main loop of most embedded firmware. Hardware description languages like Verilog have a standard pattern for them, and synthesis tools turn the transition table into flip-flops and gates.