Lesson 4.4.2.1

4.4.2.1 Finite state machines Quiz: AQA Computer Science, Unit 4

20 questions

Written by Revision Ninja · Last reviewed 11 October 2026

In partnership with Revision Ninja

Lesson 4.4.2.1, Finite state machines: 20 multiple choice questions for the AQA Computer Science (7517), Unit 4: Theory of computation, written with Revision Ninja.

Host it live on the board and students join with a game code on their own devices, or revise alone with Free Play. The answers are revealed in the game.

Host this setFree Play

The 20 questions

  1. What does a finite state machine consist of?

    • A set of random numbers
    • An infinite tape of symbols
    • A stack of unlimited depth
    • A finite set of states and transitions triggered by inputs

  2. In a state transition table, what does each row typically show?

    • A current state and input with the resulting next state
    • Only the final output of the machine
    • A list of variable names
    • Compiler warnings

  3. What distinguishes a Mealy machine from a machine with no output?

    • It has infinitely many states
    • It has no states at all and no transitions, so it cannot accept or reject any input string
    • It produces output on its transitions, depending on the current state and the input
    • It uses a stack to store its results

  4. A finite state machine with no output is mainly used to:

    • Compress images
    • Sort lists of numbers
    • Route data packets across a network
    • Accept or reject input strings belonging to a language

  5. In a state diagram, how is the start state usually shown?

    • A dashed line
    • An arrow with no source pointing into it
    • A double circle drawn around the state that is the start of the machine
    • The label END

  6. In a state diagram, how is an accepting state usually drawn?

    • It is the only state with an output
    • As a triangle
    • As a double circle
    • It is always the start state

  7. A machine accepts strings containing an even number of 1s, with its start state also accepting. Which string is accepted?

    • 10101
    • 1001
    • 1
    • 100

  8. In the machine that accepts an even number of 1s, which transition is taken from the even state on input 0?

    • It moves to the odd state
    • It moves to a dead state
    • It stays in the even state
    • It moves to a second machine

  9. A Mealy machine outputs 1 when a 1 follows a 0. For the input sequence 0, 1, 1, 0, 1, what is the output sequence?

    • 11011
    • 01101
    • 01001
    • 00000

  10. How many states does a Mealy machine need to detect a 1 that follows a 0?

    • 3
    • 1
    • 2
    • 4

  11. In that same machine, what is the next state from the state 'last input was 0' when the input is 0?

    • The state 'last input was not 0'
    • The accept state
    • The start state, which is always reached
    • The state 'last input was 0'

  12. A machine has states S1, S2 and S3, with S1 going to S2 on a, S2 going to S3 on b, and S3 accepting. Which string is accepted?

    • abb
    • a
    • ba
    • ab

  13. What is the minimum number of states needed for a machine that accepts strings with an even number of 1s?

    • 2
    • 1
    • 4
    • 3

  14. In a state diagram, what does a loop on state S labelled 1 mean?

    • Input 1 is ignored by the machine altogether
    • Input 1 resets the start state to S
    • Input 1 keeps the machine in state S
    • Input 1 halts the machine

  15. Which statement describes a machine that accepts binary strings ending in 01?

    • It accepts a string if its first input is 0
    • It accepts a string if it contains 10 anywhere
    • It accepts a string if its last two inputs are 0 followed by 1
    • It accepts a string only if its length is 2

  16. A machine has 5 states and accepts 2 input symbols. In a complete deterministic transition table, how many transitions are listed?

    • 5
    • 25
    • 7
    • 10

  17. Why is a state transition table convenient for an FSM?

    • It lists every state and input combination, making missing transitions easy to spot
    • It removes the need for inputs
    • It hides the states from the reader
    • It stores audio recordings

  18. The even-number-of-1s machine reads the input 1, 1, 1, 0. In which state does it finish?

    • The even, accepting state
    • A dead state
    • Its state is undefined
    • The odd, non-accepting state

  19. Which statement about a Mealy machine is correct?

    • Its output depends only on the time of day when the machine is switched on
    • It can only output the letter A
    • Its output depends on both the current state and the current input
    • It has no transitions

  20. A vending FSM gives a drink when the credit reaches two coins. Which element of the diagram produces that output?

    • The output is produced by the start state alone, before any coins are inserted
    • The final state alone
    • The clock signal
    • The transition that takes the machine to the credit-reached state

All AQA Computer Science quizzes