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.
| Lecture# | Date | Content | Reading |
|---|---|---|---|
| 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.
Exercises: TBA
Past examination papers can be found here.
Answers to the June 2005 exam can be found here.