AQA 7517 · Paper 1 · 4.4.1a

Finite State
Machines (FSMs)

States · Transitions · Accepting states · Section 4.4 Theory of Computation

WHAT YOU'LL LEARN

FSM components · State transition diagrams · State transition tables · Acceptance

AQA SPEC LINK

4.4.1 — Finite state machines with and without output

FSM Definition

What is a Finite State Machine?

An FSM (Finite State Automaton) is a mathematical model of computation. It has a fixed number of states and transitions between them based on input symbols.

Q — finite set of states (q₀, q₁, q₂, …)

Σ (Sigma) — input alphabet (set of valid input symbols)

δ (delta) — transition function: δ(current state, input) = next state

q₀ — start/initial state

F — set of accepting (final) states

Diagrams

State Transition Diagram Notation

FSMs are drawn as directed graphs where nodes = states and labelled arrows = transitions.

⊙ — single circle = non-accepting state

⊙⊙ — double circle = accepting (final) state

→ label on arrow = input that causes transition

→ q₀ — arrow pointing to start state (no source)

Example: FSM accepting strings ending in 'b' over alphabet {a, b}: q₀ →a→ q₀; q₀ →b→ q₁; q₁ →a→ q₀; q₁ →b→ q₁. q₁ = accepting.

State Transition Table

State Transition Tables

Equivalent to diagram but in tabular form. Rows = current states, columns = input symbols, cells = next state.

FSM: Accepts strings ending in 'b'

Current State	Input: a	Input: b
→ q₀	q₀	q₁
q₁ ✓	q₀	q₁

→ means start state; ✓ means accepting state

Acceptance

Accepting an Input String

An FSM accepts an input string if, after reading all symbols from left to right starting at q₀, the machine ends in an accepting state. Otherwise it rejects.

Trace "aab" on FSM above

q₀ →a→ q₀ →a→ q₀ →b→ q₁
Ends in q₁ (accepting) → ACCEPTED ✓

Trace "aba"

q₀ →a→ q₀ →b→ q₁ →a→ q₀
Ends in q₀ (non-accepting) → REJECTED ✗

FSM Example 2

FSM for Even Number of 0s

Accepts binary strings with an even number of 0s (including zero 0s). Alphabet: {0, 1}

State	Input: 0	Input: 1	Accept?
→ q₀ (even)	q₁	q₀	✓ YES
q₁ (odd)	q₀	q₁	✗ NO

Trace "0011": q₀→q₁→q₀→q₀→q₀ → accepted (2 zeros = even)

Mealy Machines

FSMs with Output (Mealy Machines)

A Mealy machine is an FSM that produces an output on each transition. Transitions are labelled input/output rather than just input.

Example: vending machine that outputs "dispense" when £1 is inserted and "change" when overpaid.

Transitions: q₀ →50p/nothing→ q₁; q₁ →50p/dispense→ q₀; q₁ →£1/change+dispense→ q₀

Applications

Real-World FSM Applications

Lexical analysis — compilers use FSMs to tokenise source code

Vending machines — state tracks amount inserted, transitions on coin/selection

Pattern matching — regex engines use FSMs to match patterns in strings

Network protocols — TCP uses FSM for connection state (LISTEN, SYN_SENT, ESTABLISHED…)

AQA Exam Style

Practice Question

AQA 7517 — Paper 1 Style

An FSM has states {q₀, q₁, q₂}, start state q₀, accepting state q₂. Alphabet {0,1}. Transitions: q₀→0→q₁, q₀→1→q₀, q₁→0→q₁, q₁→1→q₂, q₂→0→q₁, q₂→1→q₀.
(a) Does the FSM accept the string "001"? Show trace. [2]
(b) Does the FSM accept "0101"? Show trace. [2]
(c) Describe in words what strings this FSM accepts. [1]

[5 marks]

2 marks

(a) q₀→0→q₁→0→q₁→1→q₂. Ends q₂ = accepting ✓ ACCEPTED

2 marks

(b) q₀→0→q₁→1→q₂→0→q₁→1→q₂. Ends q₂ ✓ ACCEPTED

1 mark

(c) Strings that end with at least one 0 followed by a 1 (i.e. strings ending in "01")

Summary

Key Points to Remember

FSM = (Q, Σ, δ, q₀, F) — states, alphabet, transition function, start, accepting

State transition diagram — single circle = normal state; double circle = accepting

Acceptance — read input left to right; if end state is in F, accepted

State transition table — tabular equivalent of diagram

Mealy machine = FSM with output on transitions

🎉 Lesson complete — move to the quiz!