G51MAL Machines and Their Languages

Spring 2006



A set of lecture notes [Alt05] (PDF), [AN06] (PDF), originally developed by Dr. Thorsten Altenkirch and then updated and adapted, support the lectures.

Please note that you should not expect these notes to be a complete or even self-contained record of all that is said and discussed during the lectures. Lecture attendence is compulsory.

The book Introduction to Automata Theory, Languages, and Computation, 2nd edition [HMU01] by John E. Hopcroft, Rajeev Motwani, & Jeffrey D. Ullman is the main reference for the course. Note that this book is quite different from the classic 1979 first edition (see below). Consult the book's web pages for additional supporting material, including additional exercises with automated on-line correction, and errata. The library has got some copies of the book.

You can check prices and stock-level at the local branch of Blackwell's by following this link.

The 1979 first edition of Introduction to Automata Theory, Languages, and Computation [HU79] by John E. Hopcroft & Jeffrey D. Ullman is very thorough and a classic in the field. However, it is considerably harder than the second edition, being aimed more at PhD students or advanced undergraduates. It is now also somewhat difficult to get hold of.

One important application area for much of the material covered in the course is compilers. If you are curious, you might want to have a look at the material for the second-year module G52CMP Compilers, or you might want to browse through a book on the topic, such as the classic Compilers: Principles, Techniques, and Tools [ASU86] ("The Dragon book") by Aho, Sethi, & Ullman.


1 2 Feb Administrative Details and Introduction [Alt05, pp. 1--6; HMU01, ch. 1]
2 3 Feb Deterministic Finite Automata (DFA) [Alt05, pp. 6--8; HMU01, pp. 37--54]
3 9 Feb Nondeterministic Finite Automata (NFA) [Alt05, pp. 8--11; HMU01, pp. 55--59]
4 10 Feb Equivalence of NFA and DFA [Alt05, pp. 11--13; HMU01, pp. 60--72]
5 16 Feb Regular expressions [Alt05, pp. 13--17; HMU01, pp. 83--89, 108--113]
6 17 Feb Translating Regular Expressions into NFA [Alt05, pp. 17--25; HMU01, pp. 101--105]
7 23 Feb Proving Languages not to be Regular [Alt05, pp. 25--27; HMU01, pp. 126--131]
-- 24 Feb Cancelled!
8 2 Mar Equivalence and Minimization of Finite Automata [HMU01, pp. 154--164]
9 3 Mar Context-Free Grammars and Languages [Alt05, pp. 27-30; HMU01, ch. 5]
10 9 Mar Context-Free Grammars and Languages [Alt05, pp. 27-30; HMU01, ch. 5]
11 10 March Derivation Trees & Ambiguity [Alt05, p. 31--32; HMU01, ch. 5]
12 16 March Demonstrating Ambiguity [Alt05, pp. 31--32; HMU01, ch. 5]
13 17 Mar Disambiguating Context-Free Grammars [Alt05, pp. 31--32; HMU01, ch. 5]
14 23 Mar Pushdown Automata [Alt05, pp. 32--35; HMU01, ch. 6]
15 24 Mar Pushdown Automata [Alt05, pp. 35--36; HMU01, ch. 6]
16 18 Mar Implementing Parsers [MAL05]
16 27 Apr Context-free Grammars & Pushdown Automata [Alt05, pp. 37--38; HMU01, ch. 6]
17 28 Apr Deterministic Pushdown Automata & Parsing [Alt05, pp. 36--37, 39--44; HMU01, ch. 6]
18 4 May Turing Machines [Alt05 pp. 44--51; HMU01, ch. 8 & 9]
19 5 May Turing Machines [Alt05 pp. 44--51; HMU01, ch. 8 & 9]
20 11 May Undecidability [Alt05 pp. 44--55; HMU01, ch. 8 & 9]
21 12 May TBA [Alt05; HMU01]

Copies of lecture notes, slides, any major pieces of program code, or other electronic material used during the lectures can be found here.


Each Student is assigned to a tutorial group. This group meets once a week to discuss the coursework. You are expected to take part in the tutorials on a regular basis. Tutorials start the 2nd week of the semester (from 6/2/2006). See the tutorial page for further details.


A set of exercises is to be completed weekly and handed in before the deadline, Friday 3.30 PM each week. The answers will be marked and then discussed during the tutorials the following week. It is compulsory to hand in answers to the exercises!

Exercises: TBA


Some basic information about the exam:

Past examination papers can be found here.

Answers to the June 2005 exam can be found here.


Last updated 9 May 2006.