AQA 7517 · A-Level Computer Science · ~20 min read
What is a Finite State Machine?
A Finite State Machine (FSM) is a mathematical model of computation used to design systems that can be in one of a finite number of states at any time. The machine transitions between states based on inputs.
FSMs are used to model: vending machines, traffic lights, lexical analysers (compilers), network protocols, and game AI.
Formal definition — a 5-tuple
An FSM is defined by:
Q — a finite set of states
Σ (sigma) — a finite set of input symbols (the alphabet)
δ (delta) — the transition function: δ(state, input) → next state
q₀ — the initial (start) state
F — the set of accepting (final) states
FSM Without Output (Acceptor)
An FSM without output is called an acceptor. It reads a string of inputs and ends in either an accepting state (string is accepted) or a non-accepting state (string is rejected). Used in pattern matching and language recognition.
State transition diagram notation
States drawn as circles
Start state has an incoming arrow (→)
Accepting states drawn as double circles
Transitions drawn as labelled arrows between states
Exam tip: AQA frequently asks you to draw or trace FSMs. For transition diagrams: double circle = accepting state, arrow = transition labelled with input (and output for Mealy). For transition tables: list every state-input combination. Always trace a given string step by step through the states to determine acceptance. Know the difference between Mealy (output on transition) and Moore (output on state).
▶
Click through the slides at your own pace. Use arrow keys or click to advance.
Click slide or press arrow keys to navigate
Worksheet — 4.4.2a Finite State Machines
8 questions · instantly marked · AQA 7517 standard
Q1Define a Finite State Machine and state the five components of its formal definition.[3]
✅ Mark scheme
Mark scheme
An FSM is a model of computation with a finite number of states that transitions between states based on inputs [1]; formally defined by: Q (set of states), Σ (alphabet/input symbols), δ (transition function), q₀ (start state), F (set of accepting states) [2 — award 1 for any 2–3 components, 2 for all 5].
Q2What is the difference between an FSM without output (acceptor) and an FSM with output (transducer)?[2]
✅ Mark scheme
Mark scheme
An acceptor reads input and determines whether to accept or reject the string (ends in accepting state or not) [1]; a transducer produces an output for each input/transition [1].
Q3In a state transition diagram, how are (a) the start state, (b) accepting states, and (c) transitions shown?[3]
✅ Mark scheme
Mark scheme
(a) Start state: incoming arrow/arrow pointing to first state [1]; (b) Accepting states: double circle [1]; (c) Transitions: labelled arrows between states (labelled with the input, and output if Mealy) [1].
Q4An FSM has states {q0, q1, q2}, alphabet {0,1}, start state q0, accepting state q2. Transitions: q0→(0)→q0, q0→(1)→q1, q1→(0)→q2, q1→(1)→q1, q2→(0)→q0, q2→(1)→q1. Trace the string "110" and state whether it is accepted.[3]
✅ Mark scheme
Mark scheme
q0 →(1)→ q1 [1]; q1 →(1)→ q1 [1]; q1 →(0)→ q2 [1]; ends in q2 which is accepting — ACCEPTED. Award 1 mark per correct step, final answer implied from correct trace.
Q5Explain the difference between a Mealy machine and a Moore machine.[2]
✅ Mark scheme
Mark scheme
In a Mealy machine, the output depends on both the current state AND the current input [1]; in a Moore machine, the output depends only on the current state [1].
Q6State the difference between a deterministic FSM (DFA) and a non-deterministic FSM (NFA).[2]
✅ Mark scheme
Mark scheme
In a DFA, from each state for each input there is exactly one transition [1]; in an NFA, from each state for each input there may be zero or more transitions (including ε-transitions with no input) [1].
Q7Give two real-world applications where FSMs are used.[2]
✅ Mark scheme
Mark scheme
Any two from: vending machines [1]; traffic light controllers [1]; lexical analysers in compilers [1]; network protocol state machines [1]; game AI [1]; turnstiles / gates [1].
Q8An FSM (acceptor) for binary strings ending in '01' has states q0 (start), q1, q2 (accepting). Draw the state transition table for alphabet {0,1}.[4]
Q2Which FSM type produces an output for each transition?
Q3In a DFA, from each state for each input there is:
Q4A Moore machine's output depends on:
Q5In the formal 5-tuple definition of an FSM, δ represents:
Section B — Short Answer [5 marks]
Q6What does it mean for an FSM to "accept" a string?
Mark schemeThe FSM reads all characters of the string and ends in an accepting state (double circle state) [1].
Q7Name one application of FSMs in computer science.
Mark schemeAny one: lexical analyser in a compiler / vending machine controller / network protocol / traffic light system / game AI [1].
Q8What does the symbol Σ (sigma) represent in the FSM 5-tuple?
Mark schemeΣ is the alphabet / the finite set of input symbols [1].
Q9Why can an NFA not be directly implemented like a DFA?
Mark schemeAn NFA can have multiple transitions (or zero) for the same input from a given state [1], making it non-deterministic — it must first be converted to a DFA for direct implementation.
Q10In a Mealy machine, how are transitions labelled?
Mark schemeInput/output [1] — each transition arrow is labelled with the input symbol and the corresponding output produced.