Skip to main content
EnglandComputer ScienceSyllabus dot point

What is a finite state machine and how is it represented?

Understand finite state machines with and without output, state transition diagrams and tables, and the use of an FSM to recognise inputs or model behaviour.

A focused answer to AQA A-Level Computer Science 4.4.2, covering finite state machines with and without output, state transition diagrams and tables, and using an FSM to recognise inputs or model behaviour.

Generated by Claude Opus 4.88 min answer

Reviewed by: AI editorial process; not yet individually human-reviewed

Have a quick question? Jump to the Q&A page

Jump to a section
  1. What this dot point is asking
  2. What a finite state machine is
  3. With and without output
  4. Representations

What this dot point is asking

AQA wants you to describe a finite state machine, with and without output, represent it as a state transition diagram and a state transition table, and use an FSM to recognise valid inputs or model a system's behaviour.

What a finite state machine is

The defining limitation is in the name: the machine has only finitely many states, so all the memory it has is which state it is currently in. This is why an FSM can remember a bounded amount of history but cannot count without limit. That limitation is exactly what places the FSM at the bottom of the computation hierarchy, below the pushdown machine and the Turing machine, and it is the reason an FSM can recognise regular languages but not languages needing unbounded counting.

With and without output

The two flavours suit different tasks. The without-output machine is a recogniser: its only verdict is accept or reject, which is what makes it ideal for validating that input matches a pattern. The with-output (Mealy) machine actually does something on each step, emitting outputs that drive real behaviour, which is why it models reactive systems such as a vending machine that releases a drink and gives change in response to coin inputs.

Representations

An FSM can be drawn as a state transition diagram: circles for states (a double circle for an accepting state), an arrow into the start state, and labelled arrows for transitions (input, and for a Mealy machine the output). The same machine can be written as a state transition table listing, for each state and input, the next state (and output).

State  Input 0   Input 1
S0     S0        S1
S1     S2        S0       (accepting state shown separately)

To test an input, start in the start state and follow the transition for each symbol in turn; the final state determines acceptance, or for a Mealy machine the transitions produce the sequence of outputs. The diagram and the table are equivalent: anything one shows, the other shows, and exam questions often ask you to convert between them or to trace an input through either.

Exam-style practice questions

Practice questions written in the style of AQA exam questions on this dot point, with worked answer explainers. The year tag is the paper they imitate, not the source.

AQA 20194 marksA finite state machine without output has start state S0 and accepting state S2. Transitions are: from S0 on input 1 go to S1; from S1 on input 1 go to S2; any input 0 returns to S0. Trace the input 1 1 and the input 1 0 1, stating for each whether it is accepted.
Show worked answer →

Input 1 1: start at S0, read 1 go to S1, read 1 go to S2. The machine ends in S2, the accepting state, so the input 1 1 is accepted.

Input 1 0 1: start at S0, read 1 go to S1, read 0 return to S0, read 1 go to S1. The machine ends in S1, which is not the accepting state, so the input 1 0 1 is rejected.

Markers reward following each transition correctly from the start state and judging acceptance only by whether the final state is the accepting state (S2). The 0 resetting to S0 must be applied.

AQA 20213 marksExplain the difference between a finite state machine with output and one without output, and give one real-world system best modelled by each.
Show worked answer →

A finite state machine without output (a finite state automaton) has one or more accepting states and simply accepts or rejects an input string depending on whether it ends in an accepting state; it produces no output during processing. It is best for recognising valid inputs, for example checking that a string matches a pattern such as a valid binary multiple of three.

A finite state machine with output (a Mealy machine) produces an output as it makes each transition. It is best for modelling a system whose behaviour changes with input and produces actions, for example a vending machine that dispenses a drink or gives change, or a set of traffic lights.

Markers reward the accept-or-reject versus output-on-transition distinction and a valid system for each (a recogniser for without-output; a vending machine or traffic lights for with-output).

Related dot points

Sources & how we know this