Finite State Machines

A finite state machine (FSM), also called a finite automaton, is one of the simplest and most useful models of computation in the whole of Computer Science. The idea is deliberately austere: a machine that, at any instant, is in exactly one of a finite number of states, and that moves between those states in response to inputs according to fixed transition rules. There is no separate memory store, no variables, no counter — the only thing the machine "remembers" about everything it has seen so far is which state it is currently in. That single restriction is what makes FSMs both easy to reason about and, crucially, limited in a precise and examinable way.

Despite their simplicity, FSMs are everywhere in real systems. The part of a compiler that recognises whether a run of characters is a keyword, an identifier or a number is an FSM; the logic that tracks whether a TCP connection is listening, established or closing is an FSM; the controller inside a washing machine, a vending machine or a set of traffic lights is an FSM; and the engine that decides whether a string matches a regular expression is, underneath, an FSM. This lesson develops the H446 view: the precise definition of an FSM, the two equivalent ways of presenting one (a state-transition diagram and a state-transition table), the distinction between acceptor machines (no output beyond accept/reject) and machines with output (Mealy and Moore), the meaning of determinism, and several fully worked examples. The deep payoff — that FSMs recognise exactly the regular languages, the same class described by regular expressions — is set up here and developed in the next two lessons.

---

Spec Mapping

This lesson addresses the finite-state-machine content of H446 section 2.1 (computational methods / automata). The specification expects you to be able to:

• understand what a finite state machine is — a model with a finite set of states, a defined start state, an input alphabet, and a transition rule that fixes the next state for each (state, input) pair;
• represent an FSM both as a labelled state-transition diagram and as a state-transition table, and convert freely between the two;
• distinguish FSMs without output (acceptors/recognisers, which only accept or reject a string) from FSMs with output, and distinguish the two output conventions — Mealy (output on transitions, depending on state and input) and Moore (output on states, depending on state alone);
• understand what it means for an FSM to be deterministic, and recognise that FSMs define and recognise the regular languages;
• design an FSM for a stated requirement and trace a given FSM on a given input string, stating whether the string is accepted.

These ideas connect directly forward to regular expressions and the classification of languages (later in this course) and sideways to lexical analysis in compilers (the Translators topic) and protocol state in networking.

---

What Exactly Is a Finite State Machine?

Formally, a (deterministic) finite state machine is a five-part bundle — a quintuple:

$M = (Q,\ \Sigma,\ \delta,\ q_0,\ F)$M=(Q, Σ, δ, q0​, F)

where each part has a precise meaning:

Symbol	Name	Meaning
$Q$Q	states	a finite set of states the machine can occupy
$\Sigma$Σ	input alphabet	the finite set of input symbols the machine reads
$\delta$δ	transition function	a rule $\delta: Q \times \Sigma \to Q$δ:Q×Σ→Q giving the next state for each (state, input)
$q_0$q0​	start state	the single state the machine begins in (an element of $Q$Q)
$F$F	accepting states	the subset of $Q$Q whose members signal acceptance

The heart of the definition is the transition function $\delta$δ. It takes a current state and an input symbol and returns the next state. Reading is non-negotiable and one-way: the machine consumes the input string one symbol at a time, left to right, following $\delta$δ at each step, and it never goes back. When the input is exhausted, the machine looks at the state it has ended in — if that state is in $F$F it accepts the string, otherwise it rejects it.

The phrase that should echo through every FSM answer is the state is the only memory. An FSM cannot store a number, cannot count without bound, and cannot "look back" at characters it has already read — the entire history of the computation is compressed into one of finitely many states. This is exactly why an FSM can test "does this binary string have an even number of 1s?" (two states suffice — even-so-far and odd-so-far) but cannot test "does this string have equally many 0s and 1s?" (that needs an unbounded count, and the machine has only finitely many states). Holding that boundary firmly in mind is the single most valuable thing in this topic.

---

Acceptor (Recogniser) FSMs — Machines Without Output

The simplest FSMs have no output at all beyond the final accept/reject verdict. These are called acceptors, recognisers, or finite state automata (FSA). Their job is to answer one yes/no question about the whole input string: is this string in the language the machine recognises?

Consider an acceptor that should accept exactly those binary strings that end in "01". Three states do the job, capturing "how much of a promising ending have I just seen":

• S0 — the last symbol was not part of a "01" ending (or nothing useful seen yet); this is the start state;
• S1 — the last symbol read was a 0, so a following 1 would complete "01";
• S2 — the string read so far ends in 01; this is the accepting state.

Its transition table — note that every state has a defined move for every input symbol, which is the mark of a complete deterministic FSM:

Current state	Input 0	Input 1
→ S0 (start)	S1	S0
S1	S1	S2
*S2 (accept)	S1	S0

(By convention I mark the start state with → and accepting states with *.) Notice that reading a 0 always moves to S1 — because any 0 is a potential start of a "01" ending — and reading a 1 from S2 drops back to S0 because the most recent symbol (1) cannot itself begin a fresh "01". Reading 1 from S1 reaches the accepting S2 because we have just seen "...01".

Trace for the input "1001" (start in S0):

Step	State before	Symbol	State after
1	S0	1	S0
2	S0	0	S1
3	S1	0	S1
4	S1	1	S2

The machine ends in S2, an accepting state, so "1001" is accepted — and indeed it ends in "01".

Trace for the input "110" (start in S0): S0 →(1) S0 →(1) S0 →(0) S1. The machine ends in S1, which is not accepting, so "110" is rejected — correctly, since it ends in "10", not "01".

---

State-Transition Diagrams

A state-transition diagram is the standard visual form of an FSM. The drawing conventions are fixed and examiners expect them exactly:

• each state is a circle (or labelled node);
• each transition is an arrow from one state to another, labelled with the input symbol that triggers it;
• the start state is marked by an incoming arrow that comes "from nowhere";
• an accepting state is drawn as a double circle.

Here is the "ends in 01" acceptor as a diagram. The double-circle accepting state is shown by the transition to the final marker:

stateDiagram-v2
    [*] --> S0
    S0 --> S0 : 1
    S0 --> S1 : 0
    S1 --> S1 : 0
    S1 --> S2 : 1
    S2 --> S1 : 0
    S2 --> S0 : 1
    S2 --> [*]

The [*] --> S0 arrow marks S0 as the start state, and the S2 --> [*] arrow marks S2 as accepting. Every state has an outgoing arrow for both 0 and 1, which is what makes the machine deterministic and complete.

Exam Tip: When you draw a state-transition diagram, always (1) mark the start with an incoming "from nowhere" arrow, (2) draw accepting states as double circles, and (3) make sure every state has an outgoing arrow for every symbol in the alphabet. Dropping a transition is the single most common diagram error.

---

State-Transition Tables

A state-transition table carries exactly the same information as the diagram but in tabular form. There are two equally acceptable layouts. The first is the "one row per (state, input) pair" layout:

Current state	Input	Next state
S0	0	S1
S0	1	S0
S1	0	S1
S1	1	S2
S2	0	S1
S2	1	S0

The second is the more compact "matrix" layout (one row per state, one column per symbol), which is the one shown earlier in the acceptor section. Both describe the same machine as the diagram above.

Diagram and table are completely interchangeable — converting between them is a routine exam task. Each form has strengths:

Representation	Strength	Weakness
Diagram	Overall structure, cycles and reachability are visible at a glance	Cluttered and error-prone for many states/transitions
Table	Easy to check completeness (every cell filled) and to process algorithmically	The "shape" of the machine is hidden

A practical tip: when checking an FSM for missing transitions, use the table (a blank cell screams "undefined move"); when explaining an FSM to a human, use the diagram.

---

Finite State Machines With Output

Many real machines must do something at each step, not merely accept or reject at the end — a vending machine dispenses, a controller raises a signal. These are FSMs with output, and there are two standard conventions for where the output is attached.

Mealy machines — output on transitions

A Mealy machine produces an output that depends on both the current state and the current input. Because the output is determined by the (state, input) pair, it is written on the transition arrows, in the form input / output. Its transition function gains an output:

$\delta: Q \times \Sigma \to Q \times \Lambda$δ:Q×Σ→Q×Λ

where $\Lambda$Λ is the output alphabet. A small Mealy table:

Current state	Input	Next state	Output
S0	0	S0	A
S0	1	S1	B
S1	0	S0	C
S1	1	S1	D

Read row 2 as: "in S0, on input 1, go to S1 and emit B" — on the diagram this is the arrow S0 --> S1 : 1 / B.

Moore machines — output on states

A Moore machine produces an output that depends on the current state alone, irrespective of the input that brought it there. The output is therefore attached to the states, and the output function is simply $\lambda: Q \to \Lambda$λ:Q→Λ. You give a small output table:

State	Output
S0	X
S1	Y

…plus an ordinary (output-free) transition table for the state changes:

Current state	Input	Next state
S0	0	S0
S0	1	S1
S1	0	S0
S1	1	S1

Mealy versus Moore — the comparison examiners want

Feature	Mealy	Moore
Output depends on	current state and input	current state only
Output is written on	transitions (arrows), as input / output	states (nodes)
Typical number of states	often fewer	often more (a separate state may be needed per output value)
When output can change	as soon as the input changes	only when the state changes
Expressive power	equivalent — every Mealy machine has an equivalent Moore machine and vice versa	equivalent

The headline fact is that the two are equally powerful: any behaviour you can model with a Mealy machine you can also model with a Moore machine (typically by adding states so that each distinct output value gets its own state), and vice versa. The choice between them is one of convenience, not capability — Mealy tends to be more compact, Moore tends to make the relationship "this state means this output" easier to read.

---

Determinism

An FSM is deterministic (a DFA/DFSM) when, for every state and every input symbol, there is exactly one transition. The next state is then completely fixed by the current state and the symbol read — there is never a choice. Every machine in this lesson so far is deterministic.

A non-deterministic (NFA/NFSM) machine relaxes this: for some (state, input) pair there may be several possible next states (or none), and the machine is imagined to "explore all possibilities at once", accepting if any path reaches an accepting state.

Type	For each (state, symbol)	"Memory" of choice
Deterministic (DFSM)	exactly one next state	no choice is ever made
Non-deterministic (NFSM)	zero, one or many next states	conceptually follows all at once

The crucial theoretical fact — which underpins the next lesson — is that non-determinism adds no power: every NFSM can be converted to an equivalent DFSM (by the subset construction), and the two recognise exactly the same class of languages, the regular languages. Non-determinism can make a machine smaller or easier to design, but it can never recognise a language a deterministic machine cannot. OCR H446 questions are almost always set on deterministic machines.

---

Worked Example: A Vending Machine (FSM with output)

Requirement. A vending machine accepts 10p and 20p coins. The item costs 30p. Model it as an FSM that dispenses the item (and any change) once enough money is inserted, then resets.