Automata Theory


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]