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.