Part I. Finite automata and regular languages: determinisation, model checking, regular expressions, state minimization, the pumping lemma, Myhill-Nerode Theorem, regular inference.
Part II. Pushdown automata and context free languages: context-free grammars and languages, parsing, Chomsky-Schützenberger Theorem, modelling the behaviour of programs with recursion, the pumping lemma, pushdown automata.
Part III. Turing machines and efficient computability: Turing machines, recursive sets, universal Turing machines, decidable and undecidable problems, Rice's theorems, other models for effective computability.
After passing the course, the student shall be able to
1) give an account of the main classes of automata and structural representations (regular expression and grammars) and the equivalent language classes, and design an automaton or a grammar from an informal language description
2) relate the different classes by means of language-preserving transformations, apply the transformations to solve concrete problems and apply the transformations on concrete examples
3) for each language class, explain the main characterisation theorems, apply the theorems to solve concrete problems and explain simple theorems on concrete examples.
For higher grades, the student should also be able to
- define new language-preserving transformations [C] and show that the transformations are language-preserving [A]
- for each language class, explain more difficult theorems on concrete examples [C] and apply the theorems to prove different language properties [A].
