You are viewing a free preview of this lesson.
Subscribe to unlock all 10 lessons in this course and every other course on LearningBro.
This is a synthesis and exam-practice lesson. The previous nine lessons built the Theory of Computation strand piece by piece — abstraction, finite state machines, regular expressions, context-free grammars and BNF, Reverse Polish Notation, Turing machines, the halting problem, the classification of algorithms, and the limits of computation. Real exam questions, however, rarely respect those neat boundaries: a single question may ask you to convert a regex to an FSM, justify why a language is not regular, or relate intractability to the halting problem. The purpose of this lesson is therefore to integrate the strand and to rehearse the types of question that recur, with several full worked exam-style questions, each carrying complete banded model answers and an AO breakdown. Treat it as a dress rehearsal: read the question, attempt it yourself, then study how the bands differ.
This lesson revisits the entire Theory of Computation strand of the AQA A-Level Computer Science specification (7517), drawing together finite state machines and regular expressions (around section 4.4.2), context-free grammars / BNF (around 4.4.3), the classification of algorithms and complexity (around 4.4.4), and the model of computation, Turing machines and computability (around 4.4.5), together with the supporting stack/tree and RPN material from the algorithms area (around 4.3.3, 4.2.4 and 4.2.7). Because it is a practice lesson, it carries more specimen questions than a teaching lesson and concentrates on exam technique — precise terminology, showing working in traces, and structuring extended answers — rather than introducing new theory. The treatment is descriptive rather than a verbatim quotation of the specification.
| Topic | Core ideas to have at your fingertips |
|---|---|
| Abstraction & automation | Removing irrelevant detail; modelling a real situation then executing it on a machine |
| Finite state machines | States as bounded memory, transitions, DFA vs NFA, acceptors vs transducers (Mealy/Moore), regular languages, trace to decide acceptance |
| Regular expressions | Concatenation, alternation ` |
| Context-free languages & BNF | Terminals, non-terminals, production rules, recursion + base case, parse trees, ambiguity, the Chomsky hierarchy |
| RPN & parsing | Infix vs prefix vs postfix; shunting-yard conversion; stack evaluation; operand order for − and ÷ |
| Turing machines | Tape, head, states, transition function, configurations, Universal TM, Church-Turing thesis |
| Halting problem | Undecidability, the self-referential proof by contradiction, reduction, consequences |
| Classification of algorithms | Big-O orders, polynomial vs exponential, tractable vs intractable, P / NP / NP-complete |
| Limits of computation | Non-computable (impossible) vs intractable (infeasible) vs physical limits; quantum computing's true scope |
The strand has a single spine worth memorising: computational power grows by adding memory. A finite state machine has only its states (regular languages); add a stack and you get a pushdown automaton (context-free languages); add an unbounded read/write tape and you get a Turing machine (everything computable). Above that lies the impossible (undecidable problems), and inside the computable region lies the infeasible (intractable problems). Almost every synoptic question is testing some facet of that spine.
Theory of Computation is the most cross-referential strand on the 7517 paper, so examiners frequently bridge it to neighbouring topics. Finite state machines (§4.4.2) are the operational counterpart of regular expressions: by Kleene's theorem the two describe the same regular languages, and both sit below the Turing machine (§4.4.5) — an FSM is a strictly weaker model because it has only bounded state-memory and no tape, which is exactly why it cannot recognise balanced brackets. That limitation is the gateway to context-free languages and BNF (§4.4.3), which reappear directly in compilers and syntax analysis (§4.5.5): a grammar's production rules are what a parser uses to build a parse tree and detect syntax errors. Reverse Polish Notation (§4.3.3) is the synoptic partner of the stack abstract data type (§4.2) and of expression/binary trees (§4.2.4) — postfix is just a post-order traversal, and a stack is what evaluates it. Finally, the classification of algorithms and Big-O analysis (§4.4.4) connects to algorithm efficiency in the algorithms strand (§4.3): the tractable/intractable boundary explains why exhaustive approaches to NP-hard problems are abandoned in favour of heuristics (§4.3.6), which trade guaranteed optimality for feasible run-time.
| This topic | Links to | Why examiners pair them |
|---|---|---|
| FSMs (§4.4.2) | Regular expressions; Turing machines (§4.4.5) | Same regular languages (Kleene); FSM is a weaker machine |
| BNF / CFGs (§4.4.3) | Compilers / syntax analysis (§4.5.5) | Grammar rules drive the parser and parse tree |
| Reverse Polish (§4.3.3) | Stacks (§4.2); expression trees (§4.2.4) | Postfix = post-order; stack evaluates it |
| Big-O / classification (§4.4.4) | Algorithm efficiency (§4.3); heuristics (§4.3.6) | Intractability motivates heuristic shortcuts |
O(n) and O(n^2) compare scalability, not wall-clock time.Question: A system processes binary strings over the alphabet {0, 1}.
(a) Draw a state transition diagram for a finite state machine that accepts exactly those binary strings containing an odd number of 1s (the number of 0s is irrelevant). Mark the start state and any accepting states. (3 marks)
(b) Trace the operation of your machine on the input string 1011, showing the state after each symbol, and state whether the string is accepted. (3 marks)
(c) Write a regular expression for the language "binary strings that start with 1 and end with 0", and explain how this illustrates the relationship between regular expressions and finite state machines. (3 marks)
AO breakdown: (a) AO2 (3 marks, a correct, total, deterministic diagram); (b) AO2 (3 marks, a correct step-by-step trace and verdict); (c) AO2 (1 mark, the regex) + AO1/AO3 (2 marks, explaining the FSM–regex equivalence).
(a) Two states. One for even and one for odd. A 1 swaps between them, a 0 stays.
(b) Start at even. 1 → odd, 0 → odd, 1 → even, 1 → odd. Accepted.
(c) 1(0|1)*0. Regular expressions and FSMs are basically the same thing.
(a) States: Even (start) and Odd (accepting). On a 1 the machine switches state (Even↔Odd); on a 0 it stays in the current state. Both inputs are defined in both states.
(b)
| Step | State | Symbol | Next state |
|---|---|---|---|
| 1 | Even | 1 | Odd |
| 2 | Odd | 0 | Odd |
| 3 | Odd | 1 | Even |
| 4 | Even | 1 | Odd |
Ends in Odd, which is accepting, so 1011 is accepted (it has three 1s, an odd number).
(c) 1(0|1)*0. By Kleene's theorem every regular expression has an equivalent FSM and vice versa, so this pattern could be turned into a finite state machine accepting the same strings.
(a) The machine needs to remember only the parity of the number of 1s seen so far — one bit of information — so two states suffice:
stateDiagram-v2
[*] --> Even
Even --> Odd : 1
Even --> Even : 0
Odd --> Even : 1
Odd --> Odd : 0
Odd --> [*]
Even is the start state (zero 1s is an even count) and Odd is the single accepting state. A 1 flips the parity (Even↔Odd); a 0 leaves it unchanged (self-loop). Both symbols are defined in both states, so the machine is deterministic and total.
(b)
| Step | Current state | Symbol read | Next state |
|---|---|---|---|
| start | Even | — | — |
| 1 | Even | 1 | Odd |
| 2 | Odd | 0 | Odd |
| 3 | Odd | 1 | Even |
| 4 | Even | 1 | Odd |
The machine ends in Odd, an accepting state, so 1011 is accepted. This is correct: 1011 contains three 1s, which is an odd number.
(c) A suitable regular expression is 1(0|1)*0: a fixed leading 1, then (0|1)* to allow any sequence of bits in the middle, then a fixed trailing 0 (the shortest matching string is 10). This illustrates Kleene's theorem, which states that the regular expressions and the finite state machines describe exactly the same class of languages — the regular languages. For any regular expression one can mechanically construct an FSM that accepts precisely the matching strings (via an NFA built by Thompson's construction, then the subset construction to a DFA), and conversely every FSM's language can be written as a regular expression. The regex is the declarative description of the pattern; the FSM is the operational machine that recognises it — two views of one underlying regular language.
Examiner-style commentary: In (a) the discriminator is whether the machine is total and deterministic: the mid-band description omits the explicit self-loops on 0 and never states which state is accepting, whereas the top-band answer gives a complete diagram with start and accepting states marked and both symbols defined everywhere. Part (b) rewards a step-by-step trace; the mid-band answer reaches the right verdict but its run-on form ("1 → odd, 0 → odd…") would lose method marks if a slip occurred, while the tabulated traces protect them. In (c) all three give the correct regex, but the mark scheme wants the equivalence named and explained: "basically the same thing" earns little, whereas invoking Kleene's theorem and the declarative/operational contrast secures the AO1/AO3 marks.
Question: A programming language allows simple nested bracketed expressions such as (), (()) and (()()).
(a) Explain why a finite state machine (and hence a regular expression) cannot recognise the language of correctly balanced brackets. (3 marks)
(b) Write a set of BNF production rules that generates exactly the balanced-bracket strings (including the empty string), and identify the recursion and the base case in your grammar. (4 marks)
(c) Using your grammar, give a step-by-step derivation of the string (()). (3 marks)
AO breakdown: (a) AO1 (1 mark) + AO2/AO3 (2 marks, reasoning about bounded memory); (b) AO2 (3 marks, a correct recursive grammar) + AO1 (1 mark, identifying recursion and base case); (c) AO2 (3 marks, a correct derivation showing each rewrite).
(a) Because there can be lots of brackets and an FSM cannot handle that many.
(b)
S ::= ( S ) | S S | ε
The recursion is S and the base case is ε.
(c) S → (S) → (()).
(a) A finite state machine has a fixed, finite number of states, so it can only remember a bounded amount of information. To check balanced brackets you must track how many opening brackets are still unmatched, and that number can grow without limit, so a finite machine cannot do it.
(b)
<balanced> ::= ( <balanced> ) | <balanced> <balanced> | ε
The first two alternatives are recursive (they refer to <balanced> again) and ε (the empty string) is the base case that stops the recursion.
(c)
| Step | Sentential form | Rule |
|---|---|---|
| 0 | <balanced> | start |
| 1 | ( <balanced> ) | ( <balanced> ) |
| 2 | ( ( <balanced> ) ) | ( <balanced> ) |
| 3 | ( ( ) ) | <balanced> → ε |
(a) A finite state machine stores its entire memory in its current state, and there are only finitely many states, so it can remember only a bounded amount of information. Recognising balanced brackets requires tracking the current nesting depth — the number of ( opened but not yet closed — and this depth is unbounded (a string may nest arbitrarily deeply). By the pigeonhole principle, for a deep enough string two different nesting depths must map to the same state, after which the machine can no longer tell them apart and so cannot reliably match the closing brackets. Therefore no FSM, and hence (by Kleene's theorem) no regular expression, can recognise balanced brackets; the language is context-free but not regular, and recognising it needs the unbounded memory of a stack (a pushdown automaton).
(b)
<balanced> ::= ( <balanced> ) | <balanced> <balanced> | ε
Read the three alternatives as the three ways a balanced string is formed: a balanced string wrapped in a fresh pair of brackets (( <balanced> )); two balanced strings concatenated (<balanced> <balanced>); or the empty string. The first two alternatives are recursive — each refers to <balanced> again, which is what supplies the unbounded "memory" needed for arbitrary nesting — and the alternative ε is the base case that terminates the recursion. Brackets are only ever introduced as a matched pair (by the ( <balanced> ) rule), so the grammar can never generate an unbalanced string.
(c)
| Step | Sentential form | Rule applied |
|---|---|---|
| 0 | <balanced> | start symbol |
| 1 | ( <balanced> ) | <balanced> → ( <balanced> ) |
| 2 | ( ( <balanced> ) ) | inner <balanced> → ( <balanced> ) |
| 3 | ( ( ) ) | inner <balanced> → ε (base case) |
Every non-terminal has been rewritten away, leaving only the terminals ( and ), so (()) is in the language. The matched-pair structure of the ( <balanced> ) rule guarantees the brackets balance.
Examiner-style commentary: Part (a) is the clearest discriminator. "Lots of brackets… cannot handle that many" (mid-band) gestures at the idea but never mentions bounded versus unbounded memory or the finiteness of states; the stronger answer correctly invokes bounded memory, and the top-band answer nails it with the pigeonhole argument and names the language as context-free. In (b) all three grammars are correct, but the mark scheme also wants the recursion and base case identified, which the mid-band answer does only minimally; the top-band answer additionally explains why the grammar can never produce an unbalanced string. Part (c) rewards showing every rewrite: the one-line "S → (S) → (())" of the mid-band answer skips steps and would lose marks, whereas the tabulated derivations make each rule application explicit and end in a string of pure terminals.
Question: A calculator evaluates arithmetic using Reverse Polish (postfix) Notation and a stack.
(a) Convert the infix expression (A + B) × C − D to Reverse Polish Notation, briefly indicating your method. (2 marks)
(b) Evaluate the RPN expression 12 4 ÷ 2 − 3 × using a stack, showing the contents of the stack after each token is processed. (4 marks)
Subscribe to continue reading
Get full access to this lesson and all 10 lessons in this course.