Skip to topic
    ← Back to course topics

    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

    1. 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
    1. 1Day 1-2: Master the formal components of FSMs without output; practice drawing transition diagrams and building matching transition tables for basic string matching.
    2. 2Day 3-4: Learn Mealy machines; focus on the 'input / output' transition notation and practise building sequence detectors and serial adders.
    3. 3Day 5-6: Compare FSM computational power with regular expressions and explore limitations (such as the inability to count unbounded sequences).
    4. 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)
    Draw

    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.

    State

    Provide a concise, direct point or value without requiring extended prose, justification, or calculation steps.

    Explain

    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)
    Pitfall: Confusing Mealy and Moore machine architectures or incorrectly labelling output transitions in Mealy machines.
    ❌ Weak Answer (Loses Marks):A Mealy machine gives an output based on whatever state it is currently sitting in.
    Example improved answer:In a Mealy machine, the output is determined by both the current state and the current input. On a state transition diagram, transitions are represented using the notation 'input / output'. In contrast, a Moore machine produces outputs determined solely by the current state.
    Examiner Tip: Always write transitions for Mealy machines in the exact format 'input / output' (e.g. '0 / 1' or '1 / 0') with clearly directed arrows, and never place outputs inside the state circle.
    Pitfall: Omitting the starting state arrow or drawing accepting states with a single circle rather than concentric double circles.
    ❌ Weak Answer (Loses Marks):The student draws state circles S0, S1, and S2, circling S2 with a single outline, leaving the reader to infer where execution starts.
    Example improved answer:The start state must be explicitly indicated by an unlabelled incoming arrow pointing from nowhere into the initial state. An accepting (or halt) state in an FSM without output must be drawn as a concentric double circle.
    Examiner Tip: Before handing in your paper, audit your state transition diagram: verify that an initial incoming arrow exists, every state is unambiguously labelled, and all accepting states have double concentric rings.
    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. 1.Step 1: Identify the states needed. Let S0 = initial state (no relevant bits matched), S1 = sequence '1' has just been received.
    2. 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. 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. 4.Step 4: Construct the transition table with columns: Current State, Input, Next State, and Output.
    Final Answer: State Transition Table: - Current State: S0 | Input: 0 | Next State: S0 | Output: 0 - Current State: S0 | Input: 1 | Next State: S1 | Output: 0 - Current State: S1 | Input: 0 | Next State: S0 | Output: 1 - Current State: S1 | Input: 1 | Next State: S1 | Output: 0

    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. 1.Step 1: Start at initial state S0.
    2. 2.Step 2: Process input '1': Transition from S0 to S0 on input '1'. State remains S0.
    3. 3.Step 3: Process input '0': Transition from S0 to S1 on input '0'. State is now S1.
    4. 4.Step 4: Process input '0': Transition from S1 to S1 on input '0'. State remains S1.
    5. 5.Step 5: Process input '1': Transition from S1 to S2 on input '1'. State is now S2.
    6. 6.Step 6: Evaluation: The input string has been fully processed and the machine terminates in state S2, which is an accepting state.
    Final Answer: Trace path: S0 -> (input 1) -> S0 -> (input 0) -> S1 -> (input 0) -> S1 -> (input 1) -> S2. Since S2 is an accepting state, the string '1001' is accepted.
    Active Recall Memory Test
    What graphical symbol denotes an accepting state in an FSM without output?
    Key Fact: A double concentric circle.
    How is a transition labelled on a state diagram for a Mealy machine?
    Key Fact: Using the format 'input / output' (e.g. '1 / 0').
    What determines the output of a Mealy machine at any given time?
    Key Fact: Both the current state and the current input.
    Why can an FSM not validate whether a string contains an equal number of opening and closing parentheses for any arbitrary length?
    Key Fact: Because an FSM has a strictly finite number of states and cannot maintain an unbounded counter or stack in memory.
    Frequently Asked Questions
    What is the difference between a Mealy machine and an FSM without output?
    An FSM without output only tracks internal state changes to decide if an input string is valid, signalling success by halting in an accepting state. In contrast, a Mealy machine produces a specific output symbol on every state transition, acting as a translator or controller rather than just a pass/fail classifier.
    Do I need to know about Moore machines for AQA A-Level Computer Science?
    The AQA specification explicitly specifies Mealy machines as the primary model for FSMs with output. While understanding that Moore machines output solely based on the state itself is good context, exam questions focus almost exclusively on Mealy machines where transitions are labelled 'input / output'.
    What makes an FSM deterministic rather than non-deterministic?
    An FSM is deterministic (a DFA) if, for every state, there is exactly one defined transition for each possible input symbol from the alphabet, and transitions cannot happen spontaneously without an input. A non-deterministic FSM (NFA) can have zero, one, or multiple transitions for the same input symbol from a single state.
    Can an FSM have more than one start state?
    No. A deterministic finite state machine must have exactly one single start state, represented on diagrams by an incoming arrow originating from nowhere. Having multiple start states introduces non-determinism, which violates standard DFA rules.
    Why are finite state machines considered less powerful than Turing machines?
    FSMs have strictly limited memory represented solely by their predefined, fixed number of states. Turing machines have access to an infinitely expandable tape memory, allowing them to read, write, count to arbitrary numbers, and compute any algorithm that is theoretically computable.