Finite State Machines

A finite state machine (FSM) is an abstract model of computation that processes an input sequence one symbol at a time and changes state based on each symbol received. At any moment, the machine is in exactly one of a finite number of states.

An FSM is defined by five components:

Component	Description
A finite set of states	The possible configurations of the machine
An input alphabet	The set of symbols the machine can receive
A transition function	Rules that define the next state for each (current state, input) pair
A start state	The state the machine begins in
A set of accepting states (for FSMs without output)	States that indicate a valid/accepted input string

FSMs are used throughout computing: in lexical analysers (recognising valid tokens in source code), network protocol design, input validation, and digital circuit design. The key insight is that many useful computational tasks can be performed without any memory beyond "which state am I currently in."

AQA requires two types: FSMs without output (which accept or reject strings) and Mealy machines (FSMs with output, where each transition produces an output symbol).

A state transition diagram is the standard graphical representation of an FSM. Each component of the machine maps to a specific visual element:

Component	Diagram notation
State	Circle labelled with the state name
Start state	Circle with an arrow pointing to it from outside (no source state)
Accepting state (FSMs without output)	Double circle
Transition	Arrow from one state to another, labelled with the input symbol
Self-loop	Arrow from a state back to itself

Example — FSM over {0, 1} accepting strings that contain an even number of 1s:

States: $q_0$ (start, accepting), $q_1$

Transitions:

• $q_0$ on input 0 → $q_0$ (self-loop: receiving a 0 does not change parity)
• $q_0$ on input 1 → $q_1$ (one 1 seen so far — odd count)
• $q_1$ on input 0 → $q_1$ (self-loop: 0 does not change parity)
• $q_1$ on input 1 → $q_0$ (second 1 seen — back to even count)

$q_0$ is a double circle (accepting). The machine ends in $q_0$ — and therefore accepts — if and only if the number of 1s in the input string is even (including zero 1s).

When drawing a diagram: label each arrow with the input symbol that causes that transition. If two different inputs from the same state lead to the same destination, either draw two separate arrows or label one arrow with both symbols separated by a comma.

A state transition table is the tabular equivalent of a state transition diagram. It lists every (current state, input) combination and the resulting next state.

For the even-number-of-1s FSM above:

Current state	Input: 0	Input: 1
$q_0$ (start, accept)	$q_0$	$q_1$
$q_1$	$q_1$	$q_0$

State transition tables and diagrams contain identical information. A table is unambiguous and easy to construct; a diagram makes the overall structure and flow more immediately visible. Exam questions may give either and ask you to produce the other.

Reading a table: each row is a state; each column is an input symbol. The cell at (row, column) gives the next state. To trace a string, start at the start state and look up each input symbol in sequence.

Constructing a table from a description: list all states as rows, all input symbols as columns, then fill in each cell by applying the transition rules.

The transition function must be total for a complete FSM — every (state, input) pair must have a defined next state. If some inputs from a state lead nowhere valid, a dead state (also called a reject/trap state) is added, with all transitions from it looping back to itself.

A trace determines whether a given input string is accepted or rejected by an FSM without output. A string is accepted if processing all its symbols leaves the machine in an accepting state.

Worked trace — does the string "10110" contain an even number of 1s?

Using the even-1s FSM ($q_0$ = accepting, start):

Step	Current state	Input symbol	Next state
Start	$q_0$	—	—
1	$q_0$	1	$q_1$
2	$q_1$	0	$q_1$
3	$q_1$	1	$q_0$
4	$q_0$	1	$q_1$
5	$q_1$	0	$q_1$

Final state: $q_1$ — not an accepting state. Rejected.

Check: "10110" contains three 1s (an odd number). Correct — the FSM correctly rejects it. ✓

Does "1010" get accepted?

Start: $q_0$ → input 1 → $q_1$ → input 0 → $q_1$ → input 1 → $q_0$ → input 0 → $q_0$

Final state: $q_0$ — accepting. Accepted. "1010" contains two 1s (even). ✓

A Mealy machine is an FSM that produces an output symbol on each transition. The output depends on both the current state and the current input. Unlike FSMs without output, Mealy machines do not have accepting states — they produce a string of output symbols as they process the input.

Transition notation for Mealy machines: each arrow is labelled input/output — the input that triggers the transition followed by the output produced.

Example — a binary parity machine:

This Mealy machine reads a sequence of bits and outputs after each bit whether the total number of 1s seen so far is even (E) or odd (O).

States: $q_{even}$ (start), $q_{odd}$

Current state	Input: 0	Input: 1
$q_{even}$	$q_{even}$ / E	$q_{odd}$ / O
$q_{odd}$	$q_{odd}$ / O	$q_{even}$ / E

Each cell shows: next state / output symbol. As a diagram, each arrow is labelled input / output:

The output is produced at the moment of each transition — one output symbol per input symbol.

Worked trace — input string "1 0 1 0" through the parity Mealy machine:

Step	Current state	Input	Next state	Output
1	$q_{even}$	1	$q_{odd}$	O
2	$q_{odd}$	0	$q_{odd}$	O
3	$q_{odd}$	1	$q_{even}$	E
4	$q_{even}$	0	$q_{even}$	E

Output sequence: O, O, E, E

Interpretation: after the 1st bit (one 1 seen) — odd. After the 2nd bit (still one 1) — odd. After the 3rd bit (two 1s seen) — even. After the 4th bit (still two 1s) — even. ✓

Converting a Mealy machine state transition diagram to a table:

To construct the table from a diagram: list all states as rows, all input symbols as columns, and for each cell write the next state and output symbol, separated by a forward slash. The same information is in both representations.

AQA only requires Mealy machines for FSMs with output. Moore machines (where output depends on the current state only, not the input) are not in the specification and should not appear in exam answers.

1. Forgetting the start state marker

In a state transition diagram, the start state must be indicated by an incoming arrow from outside — not just by labelling it "start" in text. If the start state is not clearly marked, the diagram is incomplete.

2. Omitting the double circle for accepting states

Accepting states in FSMs without output require a double circle. A single circle, even if the state is labelled "accept", does not use the standard notation and will lose marks.

3. Labelling Mealy transitions as "input" only

Mealy machine transitions must show both input and output in the format input/output on each arrow. Writing only the input symbol produces a diagram that looks like an FSM without output — different semantics, and an incorrect answer.

4. Including Moore machine logic

Moore machines produce output based on the current state (not the transition). The AQA spec only requires Mealy machines. If a question asks for an FSM with output, use Mealy (output on transitions), not Moore (output on states).

5. Stopping the trace before consuming all input

A string is accepted or rejected based on the state after all input symbols have been consumed. Stopping mid-trace at the first accepting state encountered is incorrect — the machine must process the entire string before the accept/reject decision is made.