Mission 1 · Spec 4.4.1
Abstraction and automation
Problem solving, following and writing algorithms, the many kinds of abstraction, decomposition, composition and automation.
- Starter 5 min
- Learn 15 min
- Lab 15 min
- Quiz 10 min
- Exam 15 min
The Königsberg bridges
Euler solved a puzzle about walking across seven bridges by drawing the land as dots and the bridges as lines. What did he throw away, and why did it help?
Reveal
Everything except which land masses the bridges connect. This representational abstraction turned a messy real-world problem into a graph he could reason about.
Types of abstraction
| Type | Meaning |
|---|---|
| Representational | A representation arrived at by removing unnecessary details |
| Generalisation / categorisation | Grouping by common characteristics ("is a kind of" hierarchy) |
| Information hiding | Hiding all details of an object that don't contribute to its essential characteristics |
| Procedural | Abstracting the actual values used in a computation, giving a procedure that works for any inputs |
| Functional | Hiding the method of computation, leaving just input → output |
| Data | Hiding how data is represented, so new types can be built from existing ones (e.g. a stack from an array) |
| Problem reduction | Reducing a problem to one that has already been solved |
Decomposition breaks a problem into sub-problems; composition builds a solution by combining procedures or data objects. Automation means putting models (abstractions of real-world objects and phenomena) into action to solve problems: creating algorithms, implementing them in code, implementing models in data structures and executing the code.
Which kind of abstraction?
Exam-style questions
1. Explain the difference between procedural abstraction and functional abstraction.
[2 marks]Mark scheme
- Procedural abstraction abstracts away the actual values, producing a general procedure / computational method (1)
- Functional abstraction goes further, hiding the method so only the input-output relationship remains (1)
TUTOR NOTES
- Exam habit: AQA uses these exact terms; learn one example of each.
Mission 2 · Spec 4.4.2
Finite state machines, sets and regular expressions
FSMs with and without output, state transition diagrams and tables, set notation and operations, regular expressions and regular languages.
- Starter 5 min
- Learn 20 min
- Lab 25 min
- Quiz 10 min
- Exam 15 min
The turnstile
A turnstile is locked. Insert a coin and it unlocks; push through and it locks again. Pushing when locked does nothing. How many states does it have?
Reveal
Two: Locked and Unlocked. Inputs cause transitions between states. That's a finite state machine.
Key ideas
FSMs
A finite set of states, a start state, inputs that cause transitions, and (for acceptors) accepting states drawn as double circles. Shown as a state transition diagram or table.
Mealy machines
FSMs with output: each transition is labelled input/output. They don't have accepting states.
Sets
Unordered collections of distinct values, e.g. A = {1, 2, 3} or {x | x ∈ ℕ ∧ x ≥ 1} (set comprehension). Operations: membership ∈, union ∪, intersection ∩, difference \, subset ⊆, proper subset ⊂, Cartesian product ×. Sets can be finite, infinite and countably infinite; cardinality = number of elements.
Regular expressions
Describe sets of strings: * zero or more, + one or more, ? zero or one, | alternation, ( ) grouping. A language is regular if it can be described by a regular expression, or equivalently recognised by an FSM.
FSM simulator
Regular expression challenges
Set operations
Exam-style questions
1. Write a regular expression for the set of binary strings that start with 1 and end with 0.
[2 marks]Mark scheme
1(0|1)*0(2)- 1 mark for correct start and end but an incorrect middle
2. Explain the difference between a finite state machine with outputs (Mealy machine) and one without.
[2 marks]Mark scheme
- A Mealy machine produces an output on each transition (transitions labelled input/output) (1)
- An FSM without output accepts or rejects the input depending on whether it ends in an accepting state (1)
TUTOR NOTES
- Lab prompt: for the "multiple of 3" machine, try 110, 1001 and 1111. Can the student explain why it works?
- There is a full-screen FSM builder on the site for designing machines.
Mission 3 · Spec 4.4.3
Context-free languages
Backus-Naur Form and syntax diagrams, and why some languages can't be described with regular expressions.
- Starter 5 min
- Learn 15 min
- Lab 20 min
- Quiz 10 min
- Exam 15 min
Matching brackets
Can a regular expression check that every ( in an expression has a matching ), however deeply nested?
Reveal
No: an FSM has a fixed number of states, so it can't count arbitrarily deep nesting. BNF, which allows recursive rules, can describe it. Such languages are context-free.
Key ideas
BNF
Rules of the form <name> ::= alternative | alternative. Non-terminals appear in angle brackets; terminals are literal symbols. Rules can be recursive.
Syntax diagrams
A visual form of the same rules: paths through boxes (non-terminals) and circles (terminals), with loops for repetition.
Programming language syntax is usually defined in BNF, and compilers use it during syntax analysis.
BNF tester
Edit the rules and test strings.Exam-style questions
1. Write BNF rules for a <binary>, which is one or more binary digits.
[2 marks]Mark scheme
<bit> ::= 0 | 1(1)<binary> ::= <bit> | <bit><binary>(1)
2. Explain why BNF can describe some languages that regular expressions cannot.
[2 marks]Mark scheme
- BNF rules can be recursive / nest to any depth (1)
- so it can describe structures such as balanced brackets, which need unlimited memory that a regular expression / FSM doesn't have (1)
TUTOR NOTES
- Lab prompt: write a grammar for strings like 01, 0011, 000111 (n zeros then n ones).
Mission 4 · Spec 4.4.4
Classification of algorithms
Comparing algorithms, the maths behind Big O, orders of complexity, tractable and intractable problems, and the limits of computation, including the halting problem.
- Starter 5 min
- Learn 20 min
- Lab 15 min
- Quiz 10 min
- Exam 15 min
Will it ever finish?
Could anyone write a program that looks at any other program and tells you whether it will eventually stop or loop forever?
Reveal
No. Alan Turing proved this in 1936: the halting problem is unsolvable. Some problems cannot be solved by any algorithm, however powerful the computer.
Key ideas
Comparing algorithms
By time and space (memory) complexity, as a function of input size. Big O gives the order of growth, ignoring constants and lower-order terms.
Functions
A function maps each value in its domain to one value in its codomain. Linear, polynomial, exponential and logarithmic functions describe growth rates.
Tractable and intractable
Tractable problems have a polynomial-time (or better) solution. Intractable problems have no known polynomial-time solution, so heuristic methods give approximate answers, e.g. the travelling salesman problem.
Computable and non-computable
Some problems can't be solved algorithmically at all. The halting problem shows there are limits to what can be computed.
Growth chart
Classify the problem
Exam-style questions
1. Explain what is meant by an intractable problem and how such problems are often approached.
[3 marks]Mark scheme
- A problem with no polynomial (or better) time solution (1)
- so it can't be solved in a reasonable time for large inputs (1)
- Heuristic methods are used to find good-enough / approximate solutions (1)
2. Explain the significance of the halting problem.
[2 marks]Mark scheme
- It is unsolvable: no program can decide, for every program and input, whether it halts (1)
- It shows that some problems are non-computable / there are limits to computation (1)
TUTOR NOTES
- Misconception: intractable means impossible. It can be solved, just not in practical time for large inputs.
Mission 5 · Spec 4.4.5
Turing machines
The Turing machine as a model of computation, transition functions and state diagrams, and the universal Turing machine.
- Starter 5 min
- Learn 15 min
- Lab 20 min
- Quiz 10 min
- Exam 15 min
The simplest computer
What is the least you would need to build a machine that can compute anything a laptop can (given enough time and memory)?
Reveal
A tape of cells, a head that reads and writes one symbol, and a finite set of rules. That's a Turing machine, and anything computable can be computed by one.
Key ideas
Components
A finite set of states (including a start state and halting states), a finite alphabet of symbols, an infinite tape of cells, and a read/write head that moves one cell left or right.
Transition function
δ(current state, symbol read) = (new state, symbol to write, direction). Also shown as a state transition diagram.
Universal Turing machine
A Turing machine that can simulate any other Turing machine, given its description and input on the tape. It is the theoretical basis of the stored-program computer.
Why it matters
It provides a general model of computation and a definition of what is computable.
Turing machine simulator
Exam-style questions
1. Explain the importance of the universal Turing machine.
[2 marks]Mark scheme
- It can simulate any other Turing machine by reading its description from the tape (1)
- so a single machine can perform any computation: the basis of the stored-program concept / general-purpose computers (1)
2. Trace the "binary increment" machine in the lab on the input 1011, giving the final tape.
[3 marks]Mark scheme
- Head moves right to the first blank in state q0 (1)
- In q1, the rightmost 1s become 0 moving left until a 0 is found (1)
- That 0 becomes 1 and the machine halts: final tape 1100 (1)
TUTOR NOTES
- The site also has a full Turing machine simulator for designing new machines.