Finite state machines (FSMs) with and without output — AQA A-Level Computer Science
A finite state machine (FSM) is a computational model consisting of a finite number of states, transitions triggered by inputs, and optional outputs, used to design sequential logic and language recognisers. In AQA A-Level Computer Science, FSMs without outputs act as decision logic or recognisers via accepting states, while FSMs with outputs (Mealy machines) generate an output value mapped directly to input transitions.
Finite state machines (FSMs) with and without output explained
A finite state machine (FSM) is a model made of a finite set of states, a start state, and transitions that move the machine from one state to another in response to input.
Read the full explanation
A state transition diagram draws each state as a circle and each transition as an arrow labelled with the input (for a machine without output) or with the input/output pair (for a Mealy machine). A state transition table lists the current state and input in rows or columns and gives the next state, and, for a Mealy machine, the output. To interpret a diagram, trace the path from the start state, following the arrow whose label matches each input in turn. To construct one, identify every state, then add a transition for each input from each state. For example, a machine that outputs 1 whenever the input sequence ends in 01 has an output on the transition that completes the pattern.
Your focus
- Be able to draw and interpret simple state transition diagrams and state transition tables for FSMs with no output and with output (Mealy machines only).
Which command word is this?
Produce a clear, fully labelled graphical diagram. For FSMs, include directional arrows, the start arrow, distinct state labels, double circles for accepting states, and correct transition labels.
Finite state machines (FSMs) with and without output exam tips
Topic Overview
A finite state machine (FSM) is an abstract model of computation fundamental to computer science. It consists of a predetermined, finite set of states, an input alphabet, and a transition function that maps a current state and input symbol to a subsequent state. FSMs are divided broadly into machines without output (used as language recognisers or sequence validators) and machines with output (such as Mealy and Moore machines used for control systems, transducers, and hardware logic).
Understanding FSMs allows students to model deterministic behaviour, automate lexical analysis in compiler design, and verify hardware protocols. In the AQA A-Level specification, mastery of FSMs connects theoretical computation directly to regular languages, Turing machines, and practical electronic components like digital counters and traffic light controllers.
Key Concepts
- →Formal definition of an FSM: A 5-tuple consisting of a finite set of states (Q), an input alphabet (Sigma), a transition function (delta), an initial state (q0), and a set of accepting states (F).
- →FSMs without output: Also known as finite state automata, these process an input stream and accept or reject the string depending on whether the machine terminates in an accepting (double-ring) state.
- →Mealy machines: FSMs with outputs where the output value is determined by both the current state and the current input symbol (labelled as 'input / output' on transitions).
- →State transition diagrams and tables: Dual visual and tabular representations used to specify complete state spaces, transitions, and corresponding outputs without ambiguity.
- →Deterministic vs Non-deterministic: AQA focuses primarily on Deterministic Finite Automata (DFAs), where exactly one valid transition exists for each possible input symbol from any given state.
Marking Points
- Draws each state as a labelled circle and marks the start state clearly.
- Labels each transition arrow with the input for a machine without output.
- Labels each transition arrow with input/output for a Mealy machine.
- Includes a next-state entry for every combination of state and input in a state transition table.
- Gives the output in the table alongside the next state for a Mealy machine.
Examiner Tips
- 💡Check that every state has a transition for every possible input.
- 💡When tracing a diagram, write down the state after each input to avoid losing your place.
- 💡Keep the input/output notation consistent throughout a single diagram or table.
- 💡Always check that every state has an outgoing transition for every symbol in the defined alphabet when designing a deterministic FSM.
- 💡When drawing state transition diagrams, ensure arrowheads are unambiguously pointing to the intended destination state, and write transition labels legibly beside the line.
- 💡If an exam question asks for a state transition table, include all four standard column headers: 'Current State', 'Input', 'Next State', and 'Output' (if output is present).
Common Mistakes
- Omits the output label on transitions of a Mealy machine; add the output after the input on each arrow.
- Leaves a state and input combination out of the table; add a row or column entry for every combination.
- Confuses a Mealy machine with a Moore machine by attaching outputs to states; in a Mealy machine the output belongs to the transition.
- Believing an FSM can recognise any pattern: Students often fail to realise FSMs have strictly finite memory and therefore cannot count arbitrary depths or balance arbitrarily nested parentheses (which requires a pushdown automaton).
- Assuming Mealy outputs occur upon entering a state: Outputs in a Mealy machine are generated during the transition itself, not stored within the destination state.
- Omitting dead/trap states in recognisers: If an input makes acceptance impossible, a fully specified deterministic FSM must transition explicitly to an absorbing error state, rather than just omitting the transition arrow.
Revision Plan
- 1Day 1-2: Master the formal components of FSMs without output; practice drawing transition diagrams and building matching transition tables for basic string matching.
- 2Day 3-4: Learn Mealy machines; focus on the 'input / output' transition notation and practise building sequence detectors and serial adders.
- 3Day 5-6: Compare FSM computational power with regular expressions and explore limitations (such as the inability to count unbounded sequences).
- 4Day 7: Complete timed AQA past-paper questions focusing on state transition tables, diagram completions, and 4-6 mark design problems.
Exam Question Types
- 📋Diagram Completion: You are given an incomplete state transition diagram and must add missing states, transitions, or 'input / output' labels to satisfy a given specification.
- 📋Table to Diagram Conversion: Converting a provided state transition table into an equivalent state transition diagram, or vice versa.
- 📋String Trace and Evaluation: Tracing a specific input string through an FSM and stating whether it is accepted or writing down the exact output sequence produced.
- 📋Theoretical Explanations: Short-answer questions defining terms such as 'transition function', 'accepting state', or explaining the operational distinction between Mealy and Moore machines.
Command Word Expectations (AQA)
Produce a clear, fully labelled graphical diagram. For FSMs, include directional arrows, the start arrow, distinct state labels, double circles for accepting states, and correct transition labels.
Provide a concise, direct point or value without requiring extended prose, justification, or calculation steps.
Set out purposes, mechanics, or reasons in logical progression using precise technical vocabulary (e.g. referencing states, inputs, transitions, and outputs).
How Students Lose Marks (Examiner Pitfalls)
Step-by-Step Worked Solutions
Question: Draw a state transition table for a Mealy machine that accepts a serial binary input stream and produces an output of '1' whenever the sequence '10' is detected, and '0' at all other times. The machine must allow overlapping sequences.
- 1.Step 1: Identify the states needed. Let S0 = initial state (no relevant bits matched), S1 = sequence '1' has just been received.
- 2.Step 2: Determine transitions from S0: On input '0', output is '0' and remain in S0. On input '1', output is '0' and transition to S1.
- 3.Step 3: Determine transitions from S1: On input '1', output is '0' and remain in S1 (preserving the potential leading '1' of a new sequence). On input '0', the sequence '10' is completed, so output is '1' and transition back to S0.
- 4.Step 4: Construct the transition table with columns: Current State, Input, Next State, and Output.
Question: Trace the execution of an FSM without output configured to recognise strings ending in '01' over the alphabet {0, 1}. The states are S0 (start), S1 (last bit was 0), and S2 (accepting, sequence ended in 01). Trace the input string '1001'.
- 1.Step 1: Start at initial state S0.
- 2.Step 2: Process input '1': Transition from S0 to S0 on input '1'. State remains S0.
- 3.Step 3: Process input '0': Transition from S0 to S1 on input '0'. State is now S1.
- 4.Step 4: Process input '0': Transition from S1 to S1 on input '0'. State remains S1.
- 5.Step 5: Process input '1': Transition from S1 to S2 on input '1'. State is now S2.
- 6.Step 6: Evaluation: The input string has been fully processed and the machine terminates in state S2, which is an accepting state.