A-Level Computer Science: Turing Machines, BNF, Reverse Polish and Sets

This material trains the theory of computation topics that sit alongside finite state machines and the halting problem in A level Computer Science: Turing machines, grammars written in Backus-Naur form, Reverse Polish notation, the notation of sets, and finite state machines that produce output. It is for Year 12 and Year 13 students, and it matches most closely the specifications that include this content, for example AQA's.

The quiz has twelve questions, and every machine, grammar and set is written out in full in the question. Two questions trace one Turing machine given by its transition function: the tape after it runs on 1011, and the number of transitions it needs on 111, where the blank square matters. A third asks why the Universal Turing Machine matters. Two questions use BNF: picking the one string a recursive rule accepts, and explaining why BNF can describe balanced brackets when a regular expression cannot. Two use Reverse Polish notation: converting an infix expression with a bracket, and evaluating a postfix expression with a stack. Three use set notation: the cardinality of a union built from a set comprehension, the elements of a Cartesian product, and the difference between a subset and a proper subset. The last two are about Mealy machines: tracing one whose outputs mark every change in the input, and how a machine with output differs from one without.

Every explanation traces the machine or the stack step by step and says what the wrong options got wrong, such as forgetting that ℕ includes 0 in this convention or writing a pair in the wrong order.

The flashcards cover the parts of a Turing machine, transition functions, halting states, the Universal Turing Machine, BNF, recursion in grammars, syntax diagrams, Reverse Polish notation and why it is used, set comprehension, cardinality, Cartesian products, countable sets and Mealy machines.

The written work has eight longer tasks to answer on paper: describing and tracing a Turing machine, the importance of the Universal Turing Machine, testing strings against a BNF grammar for signed integers, converting two expressions to Reverse Polish notation and evaluating one with a stack, why Reverse Polish notation and stacks go together, set operations with a Cartesian product, designing a Mealy machine that tracks parity, and writing BNF for a variable declaration. Each task has a model answer and the points a marker would look for.

There is also a short oral practice with an examiner, who writes out each machine or grammar in full, asks one question at a time and gives brief feedback at the end.

The content is based on the theory of computation sections of the A level specifications, for example AQA 7517 sections 4.3.3 (Reverse Polish), 4.4.2 (finite state machines with output and the maths of sets), 4.4.3 (BNF and syntax diagrams) and 4.4.5 (Turing machines).

• Trace a Turing machine from its transition function and explain the Universal Turing Machine
• Check strings against BNF production rules and write simple recursive rules
• Explain why BNF can describe languages that regular expressions cannot
• Convert between infix and Reverse Polish notation and evaluate RPN with a stack
• Use set comprehension, union, intersection, difference, subsets and Cartesian products
• Trace and design Mealy machines

Practice material written by Zestly, based on the theory of computation content of the A level Computer Science specifications (for example AQA 7517 sections 4.3.3, 4.4.2, 4.4.3 and 4.4.5).