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.

How many questions?

What the quiz covers

  1. Alphabets, strings and languages (4 questions)
  2. Deterministic finite automata (DFA) (4 questions)
  3. Designing DFAs: memory, complement and product (4 questions)
  4. Nondeterministic finite automata (NFA) (4 questions)
  5. From NFA to DFA: the subset construction (4 questions)
  6. Minimising a DFA (4 questions)
  7. Regular expressions (4 questions)
  8. From regular expression to NFA: Thompson's construction (4 questions)
  9. Beyond regular: the pumping lemma (4 questions)
  10. Context-free grammars (4 questions)
  11. Parsing with the CYK algorithm (4 questions)
  12. Pushdown automata (4 questions)
  13. Turing machines (4 questions)
  14. Decidability and the halting problem (4 questions)
  15. P, NP and NP-completeness (4 questions)