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 lesson consolidates the key topics from the Theory of Computation unit and provides exam-style guidance. Use this to review the major concepts, practise applying them, and prepare for the types of questions that appear in A-Level Computer Science exams.
| Topic | Key Concepts |
|---|---|
| Abstraction & Automation | Removing unnecessary detail; modelling problems for computation |
| Finite State Machines | States, transitions, DFA, NFA, regular languages, state diagrams and tables |
| Regular Expressions | Concatenation, alternation (|), Kleene star (*), equivalence with FSMs |
| Context-Free Languages & BNF | Production rules, non-terminals, terminals, parse trees, Chomsky hierarchy |
| RPN & Parsing | Infix to postfix conversion, stack-based evaluation, shunting-yard algorithm |
| Turing Machines | Tape, head, states, transition function, Church-Turing thesis, UTM |
| Halting Problem | Undecidability, proof by contradiction, implications |
| Algorithm Classification | P, NP, NP-complete, tractable, intractable, computable, heuristics |
| Limits of Computation | Theoretical, practical, and physical limits |
Subscribe to continue reading
Get full access to this lesson and all 10 lessons in this course.