Lecture notes
The course is divided into 4 modules.
Module 1
Mathematical Finite state machines, regular languages and properties of regular languages.
Detecting non-regular languages, the Pumping Lemma. Myhill-Nerode relation and characterising Regular languages.
[slides]
Module 2
Generalised models of computation: 2DFAs, finite state transducers, pushdown automata and Context-free languages.
[slides]
Module 3
Introduction to Turing machines and computability.
Equivalence between different versions of Turing machines.
Turing decidable and Turing recognisable languages. Properties of these languages.
Diagonalisation. Undecidability of languages. The halting problem and other undecidable problems.
[slides]
Module 4
Effective computation: Turing machines with resource bounds. Introduction to
complexity theory. Definitions of P, NP, EXP, NEXP. Introduction to space bounded classes such as Log, NLog.
Savitch's theorem.
[slides]
Tutorials problems
Tutorials 1-12 and extra problem sheet.
[PDF]