Theory of Computation: final assessment

This covers the whole course. Take it after the last module.

Final quiz

1. What is |ε|, the length of the empty string?
2. Which machine recognises exactly the regular languages?
3. Which of these describes a context-free language that is not regular?
4. Which problem is undecidable?
5. Which class contains problems with certificates that can be checked in polynomial time?
6. An NFA has 4 states. What is the most states its subset DFA can have?
7. What does re.fullmatch('(a|b)*b', 'abba') return?
8. Which construction shows that regular languages are closed under intersection?
9. In which order does CYK fill its table?
10. A DFA with 7 states reads a word of length 10. What must happen?
11. Which PDA move pushes without popping?
12. Rice's theorem says that non-trivial questions about what a program computes are…
13. If someone found a polynomial-time algorithm for 3-colouring graphs, what would follow?
14. Why are nondeterministic and deterministic finite automata equal in power, but not pushdown automata?
15. The remainder DFA for 'binary numbers divisible by 4' has 4 states. How many does its minimal DFA have?
16. A recogniser for language L exists, and one for its complement too. What follows?

Practical assessment: Build a lexer from regular expressions

Without using hints or the re module, write a program that reads token definitions as regular expressions (identifier, number, operator, whitespace) and splits source text into tokens using automata you build yourself.

Final project

A regular-expression engine: Build a program that compiles a regular expression into a minimal DFA and uses it to match text, without the re module.

How it is evaluated

To complete this course