AQA 7517 4.4.2.1: Finite state machines (FSMs) with and without output
The free BugBot lessons that teach this point, a robot to try it on, and the past-paper questions that test it.
What it covers
In robotics lesson 5.2 you gave a robot a plan by keeping a state variable and changing it when something happened. Theory of computation takes that idea and makes it exact. A finite state machine (FSM) is the simplest model of a computer there is: it has no variables and no memory apart from which state it is in. This module climbs from FSMs to regular expressions, grammars and finally the Turing machine, and asks a question GCSE never did: what can a computer do at all?
- What an FSM is
- State transition diagrams
- State transition tables
- Tracing a run
- An FSM in Python
- Missing transitions and trap states
- Where FSMs are used
Or do it in the simulator, with tasks that mark themselves
Lessons that teach it
- A6.1 Finite state machines Theory of computation
States, transitions and accepting states; state transition diagrams and tables; tracing an FSM and running one from a table. - A6.2 Mealy machines: FSMs with output Theory of computation
Output on every transition, tracing a Mealy machine, and a search, approach and stop controller for the robot. - A6.10 Project: the mission robot Theory of computation
Validate a mission with a regular expression, carry it out with a Mealy machine, and report with sets. - A15.7 Calculation and theory questions Exam preparation
Number representation, floating point, Boolean logic, state machines and complexity answered quickly and checked.
Try it on a robot
The task from A6.1 Finite state machines, running here. Change the program and press Run.
The specification is AQA's own document; this page says which of our lessons teach point 4.4.2.1 and is not endorsed by the board.