Theory of Computation quiz: 60 questions
60 questions from the 15 lessons of Theory of Computation. Each answer is explained, with a link back to the lesson it comes from, and your best score stays on this device.
Test yourself
60 questions from this course's lessons, in a random order. See what you remember, then go back to the lessons behind the questions you missed.
What the quiz covers
- Alphabets, strings and languages (4 questions)
- Deterministic finite automata (DFA) (4 questions)
- Designing DFAs: memory, complement and product (4 questions)
- Nondeterministic finite automata (NFA) (4 questions)
- From NFA to DFA: the subset construction (4 questions)
- Minimising a DFA (4 questions)
- Regular expressions (4 questions)
- From regular expression to NFA: Thompson's construction (4 questions)
- Beyond regular: the pumping lemma (4 questions)
- Context-free grammars (4 questions)
- Parsing with the CYK algorithm (4 questions)
- Pushdown automata (4 questions)
- Turing machines (4 questions)
- Decidability and the halting problem (4 questions)
- P, NP and NP-completeness (4 questions)