LC-TOC
Theories of Computation
Automata, languages, decidability and the limits of what computers can do.
DFAs & NFAsRegular languagesContext-free grammarsTuring machinesDecidabilityComplexityLambda calculus
Question bank
Questions by topic
35 questions from 12 papers. See which topics come up in which years.
Practice modeMembers only: sign in to practise
| Topic | Summer 2012 | Summer 2016 | Resit 2022 | Summer 2022 | 2023 Formative | 2023 Summative | Mock 2023 | Summer 2023 | Summer 2024 | All |
|---|---|---|---|---|---|---|---|---|---|---|
| DFAs & NFAs | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 8 | |
| Regular languages | 1 | 1 | 2 | 1 | 1 | 1 | 1 | 1 | 9 | |
| Context-free grammars | 1 | 1 | 1 | 4 | 1 | 1 | 1 | 10 | ||
| Turing machines | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 8 | |
| Decidability | 1 | 1 | 1 | 1 | 2 | 1 | 1 | 8 | ||
| Complexity | 1 | 2 | 2 | 1 | 1 | 1 | 1 | 2 | 2 | 13 |
| Lambda calculus | 1 | 1 | ||||||||
| All questions | 4 | 5 | 4 | 4 | 3 | 5 | 4 | 3 | 3 | 35 |
Loading questions…