The parsing problem and parse trees. Recursive-descent parsing. LL(1) grammars. Excursion: Attribute grammars. Excursion: Parsing tools in the Scala language. Supplement: General definition of LL(1) grammars.
Turing machines. Extensions of Turing machines: multitrack machines, multitape machines, nondeterministic machines. Some computability theory: Turing-recognisable and Turing-decidable languages. Excursion: The halting problem, first encounter.
Undecidability of some Turing machine properties: the halting and non-emptiness problems. Other undecidability results: logic and algebra, Post's correspondence problem, the Chomsky hierarchy. Computable functions and reductions. Excursion: Post's correspondence problem.