Part I. Finite Automata and Regular Languages: determinisation, model checking, regular expressions, state minimization, proving non-regularity with 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, proving non-context-freeness with the pumping lemma, pushdown automata.
Part III. Turing Machines and Effective Computability: Turing machines, recursive sets, universal Turning machines, decidable and undecidable problems, Rice's theorem, other models of effective computability.
The overall aim of the course is to provide students with a profound understanding of computation and effective computability through the abstract notion of automata and the language classes they recognize. Along with this, the students will get acquainted with the important notions of state, nondeterminism and minimization.
After the course, the students will be able to:
1) Account for the main classes of automata and structural representations (regular expressions and grammars) and the corresponding language classes: Construct an automaton or a grammar from an informal language description [for grade E].
2) Relate the various classes by means of language-preserving transformations; apply the transformations for solving concrete problems: Apply the transformations on concrete examples [E], define new transformations [C], prove the transformations to be language-preserving [A].
3) For each language class, explain the main characterisation theorems; apply the theorems for solving concrete problems: Explain the easier theorems on concrete examples [E], explain the more difficult theorems on concrete examples [C], apply the theorems to prove various language properties [A].