Finite state machines

Push through a ticket barrier on the Underground and it does something oddly clever with almost no brain at all. It sits locked. Tap a valid card and it unlocks. Push through, and it locks again behind you. Tap again without pushing and nothing changes; shove a locked barrier and it stays firmly shut. The whole behaviour of the machine is captured by just two situations it can be in — locked or unlocked — and a handful of rules for how a card-tap or a push moves it between them.

That is a finite state machine (FSM): an abstract model of a system that reacts to a sequence of inputs. It has a finite set of states (the situations it can be in), one special start state, and a set of transitions — rules of the form "if I am in this state and I read that input, I move to that state." Nothing more. There is no memory of the past beyond the single state the machine is sitting in right now.

FSMs are everywhere in computing precisely because they are so cheap and so predictable: traffic lights, vending machines, the lexer that chops your program into tokens, the pattern-matcher behind a regular expression, the AI in a simple game, a network protocol handshake. Once you can see the states and the arrows between them, a surprising number of "reactive" systems become easy to reason about.

The four ingredients

Every finite state machine is built from the same small set of parts. Fix these in your head and you can read any FSM in the world:

States — the distinct situations the machine can be in, drawn as circles. There must be a finite number of them (that is the "finite" in the name). For the barrier: Locked and Unlocked.
Start state — the one state the machine begins in, marked by a short arrow coming from nowhere. Exactly one.
Inputs — the events the machine reads, one at a time, from a sequence. The set of possible inputs is the machine's alphabet. For the barrier the alphabet is { card, push }.
Transitions — labelled arrows between states. An arrow from Locked to Unlocked labelled card means "when in Locked and a card is read, go to Unlocked." An input can also loop an arrow straight back to the same state (a self-loop) when it changes nothing.

Some FSMs also have one or more accepting (final) states, drawn as a double circle. These matter when we use an FSM as a recogniser: feed it a whole sequence, and if it finishes in an accepting state we say the machine accepts that sequence — otherwise it rejects it. The barrier has no accepting state (it just runs forever); the binary example further down does.

A state-transition diagram: the turnstile

The picture below is a state-transition diagram for the ticket barrier. Two states, two inputs, and four transitions — one for every combination of "which state am I in?" and "what did I just read?". Step through it and watch the machine react.

Read it out loud and it is just common sense: from Locked, a card unlocks you and a push does nothing (it loops back to Locked); from Unlocked, a push takes you through and re-locks the barrier, while another card is wasted (it loops back to Unlocked). Notice the crucial property: from every state, every possible input has an arrow. The machine is never caught not knowing what to do.

The same machine as a table

A diagram is lovely for seeing the shape of a machine, but for a computer — or for a machine with many states — a state-transition table says exactly the same thing more compactly. Each row is a current state, each column is an input, and the cell is the state you move to. The diagram and the table are two views of one identical machine.

Current state	Input: card	Input: push
Locked (start)	Unlocked	Locked
Unlocked	Unlocked	Locked

Every cell is filled in — there are no gaps. That completeness is what makes an FSM deterministic: given the current state and the next input, the next state is never in doubt. Trace the input sequence card, push, push, card across the table starting from Locked and you will land on: Unlocked → Locked → Locked → Unlocked. The machine's entire response to that sequence is decided the moment you know the rules.

A recogniser: binary strings ending in 01

Here is where the accepting state earns its keep. This FSM reads a binary string one bit at a time (its alphabet is \{0, 1\}) and its job is to answer a yes/no question: does the string end in 01? We need only three states, each of which remembers just enough about what we have seen so far:

S0 — "the last bit was not a useful start" (the start state).
S1 — "the last bit was a 0" (a promising beginning).
S2 — "the last two bits were 01" (the accepting, double-circled state).

Watch how the machine slides between states. A 0 always moves it to S1 ("I have just seen a 0, so I'm ready"). From S1 a 1 completes the pattern and jumps to the accepting S2. But S2 is not a trap: read another 1 and the pattern is broken, so it falls back to S0; read a 0 and it is ready again at S1. After the last bit, ask one question: am I sitting in the double circle? If yes, the string ended in 01.

Current state	Input: 0	Input: 1
S0 (start)	S1	S0
S1	S1	S2
S2 (accepting)	S1	S0

Let's trace 1101 from S0: read 1 \to S0, read 1 \to S0, read 0 \to S1, read 1 \to S2. We finish in the accepting state, so 1101 is accepted — and indeed it ends in 01. Now trace 010: S1 → S2 → S1. We finish in S1, not S2, so 010 is rejected — correct, it ends in 10.

It never stores the two bits. Instead, the identity of the state itself is the memory: each state is a summary of everything that matters about the past. S1 means "the most recent bit was a 0" — we do not care what came before it, because for the question "does it end in 01?" nothing before the last bit can matter. This is the deep trick of FSM design: choose your states so that each one packages up exactly the history you still need, and no more. Get the states right and the arrows almost draw themselves.

An FSM in code

Because the table is the machine, translating an FSM into a program is almost mechanical: keep a state variable, then loop over the inputs looking each transition up in the table. Here is the "ends in 01" recogniser written out — feed it a string of bits and it reports accept or reject.

type State = "S0" | "S1" | "S2"; // The state-transition table, straight from the diagram above. const transition: Record<State, Record<string, State>> = { S0: { "0": "S1", "1": "S0" }, S1: { "0": "S1", "1": "S2" }, S2: { "0": "S1", "1": "S0" }, }; const accepting: State[] = ["S2"]; function accepts(input: string): boolean { let state: State = "S0"; // start state for (const bit of input) { // read one input at a time state = transition[state][bit]; // follow the labelled arrow } return accepting.includes(state); // finished in a double circle? } console.log("1101 ->", accepts("1101")); // ends in 01 -> true console.log("010 ->", accepts("010")); // ends in 10 -> false console.log("00101->", accepts("00101")); // ends in 01 -> true console.log("" + accepts("")); // empty -> false

Notice how little code it takes. The machine has no counters, no arrays of history — just a single state that is overwritten on every bit. That frugality is the whole appeal of the model.

Machines that also produce output: Moore and Mealy

The FSMs so far only accept or reject. Many real machines also need to do something — a traffic light must actually show a colour, a vending machine must actually dispense a can. FSMs with output come in two classic flavours, and A-level often names both:

Moore machine — the output depends only on the current state. Each state carries a fixed output (a traffic light in the "Green" state simply shows green). The output changes only when the state changes.
Mealy machine — the output depends on the current state and the input that triggers the transition. The output is written on the arrows, not the states, so a Mealy machine can react to an input instantly, before it has even settled into a new state.

Both are still finite state machines — same states, same transitions — they just differ in where the output is attached (on the states, or on the arrows). A pure recogniser like our "ends in 01" machine is really just a special case with a one-bit output: accept or reject.

An FSM's only memory is the single state it is currently in. It has no notebook, no stack, no tally — just "which circle am I standing in right now." Two easy consequences trip people up:

It cannot count arbitrarily high, and it cannot remember a whole history. With a finite number of states, there are only finitely many things it can distinguish. A machine to accept "the same number of 0s as 1s" for any length string is impossible as an FSM — it would need to remember a running total that grows without bound, and no fixed set of states can hold an unbounded number. This is exactly why more powerful models exist: a pushdown automaton adds a stack, and a Turing machine adds unlimited tape. The limits of the FSM are what motivate the whole rest of the theory.
Every state must have a defined transition for every input in the alphabet. If some state has no arrow for input 1, the machine is stuck the moment it reads a 1 there — the definition is incomplete. In a proper deterministic FSM the transition table has no blank cells. When a diagram looks like it is missing an arrow, that "missing" case is almost always a self-loop that was left off for tidiness.