 |
|
|
|
|
|
|
A set of lecture notes [AN07] (PDF), originally developed by Thorsten Altenkirch and then updated and adapted, support the lectures, along with electronic lecture slides [ELS12] for some of 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 attendance is compulsory. |
|
The 2006 third edition of Introduction to Automata Theory, Languages, and Computation [HMU06] by John E. Hopcroft, Rajeev Motwani and 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. You can check prices and stock-level at the local branch of Blackwell's by following this link. |
|
The 2001 second edition of Introduction to Automata Theory, Languages, and Computation [HMU01] by John E. Hopcroft, Rajeev Motwani and Jeffrey D. Ullman is essentially the same as the 3rd edition, and serves just as well for this module. Note however that the page references below are for the 3rd edition. The library has some copies of this book. |
|
The 1979 first edition of Introduction to Automata Theory, Languages, and Computation [HU79] by John E. Hopcroft and Jeffrey D. Ullman is very thorough and a classic in the field. However, it is considerably harder than the second and third editions, being aimed more at PhD students. 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 module G52CMP Compilers, or you might want to browse through a book on the topic, such as Compilers: Principles, Techniques, and Tools, known as "The Dragon Book" (see below). |
|
|
The first edition of Compilers: Principles, Techniques, and Tools [ASU86] ("The Dragon book") by Aho, Sethi and Ullman is a classic in the field of Compilers. It is sometimes referred to as the "Red Dragon Book" to distinguish it from the second edition. |
|
The second edition of Compilers: Principles, Techniques, and Tools [ALSU06] by Aho, Lam, Sethi and Ullman looks a bit more accessible than the original, and has been updated in many respects, though I haven't had chance to study it in detail. It is sometimes referred to as the "Purple Dragon Book" to distinguish it from the first edition (though be aware that the cover of the international edition doesn't feature a dragon, alas). |
|
If you need to brush up on your Haskell knowledge, I recommend Programming in Haskell [Hut07], by our own Prof. Hutton. The library should have plenty of copies, and so should the local bookshop. |
The lecture overview below is tentative. On some topics we may progress slower or faster than scheduled. If so, any references to lecture numbers will always refer to the content listed below, regardless of the date the lecture took place. Also, some topics may change slightly, especially towards the end.
Copies of slides, major pieces of program code, or any other electronic material used during the lectures, can be found here.
| Lecture | Date | Content | Reading |
|---|---|---|---|
| 1 | 2nd February | Administrative Details and Introduction | [AN07, pp. 2–5; HMU06, pp. 1–5] |
| 2 | 3rd February | Alphabets, Words and Languages | [AN07, pp. 6; HMU06, pp. 28–33] |
| 3 | 9th February | Deterministic Finite Automata (DFAs) | [AN07, pp. 7–8; HMU06, pp. 45–52] |
| 4 | 10th February | Nondeterministic Finite Automata (NFAs) | [AN07, pp. 9–11; HMU06, pp. 55–59] |
| 5 | 16th February | Equivalence between NFAs and DFAs | [AN07, pp. 11–13; HMU06, pp. 60–71] |
| 6 | 17th February | Regular Expressions (REs) | [AN07, pp. 13–17; HMU06, pp. 85–91, 115–118] |
| 7 | 23rd February | Equivalence of REs and Finite Automata | [AN07, pp. 17–25] |
| 8 | 24th February | Minimisation of Finite Automata | [AN07, pp. 25–29; HMU06, pp. 155–165] |
| 9 | 1st March | Proving Languages not to be Regular | [AN07, pp. 29–31; HMU06, pp. 127–131] |
| 10 | 2nd March | Pushdown Automata (PDAs) | [AN07, pp. 37–39; HMU06, pp. 225–229] |
| 11 | 8th March | The Language of a PDA | [AN07, pp. 39–41; HMU06, pp. 230–236] |
| 12 | 9th March | Context-Free Grammars (CFGs) | [AN07, pp. 32; HMU06, pp. 171–175, 193–205] |
| 13 | 15th March | The Language of a CFG | [AN07, pp. 33–35; HMU06, pp. 175–181] |
| 14 | 16th March | Equivalence of PDAs and CFGs | [AN07, pp. 41–43; HMU06, pp. 237–246, 252–258] |
| 15 | 22nd March | Context-Sensitive Grammars | [AN07, pp. 53–54] |
| 16 | 23rd March | Turing Machines | [AN07, pp. 49–53; HMU06, pp. 324–335] |
| 17 | 29th March | Decidability | [AN07, pp. 54–56; HMU06, pp. 315–324, 377–390] |
| 18 | 1st May | Derivation Trees and Ambiguity | [AN07, pp. 35–37; HMU06, pp. 183–186, 207–208] |
| 19 | 2nd May | Recursive-Descent Parsing | [AN07, pp. 41–43] |
Tutorials will be each Wednesday either 10-11 or 14-15. You will be assigned a group but you can switch, if you have a good reason. Participation in the tutorials is compulsory and coursework handin and feedback happens at the tutorial. Tutorials start on 15 February.
Laurence's page with the tutorial allocation.
A set of problems is to be completed weekly and handed in in person at your tutorial on Wednesday. If you are unable to come to your tutorial you may hand-in at the school office on Thursday but note this is considered a late handin and incurs a penalty of 10%. You are also supposed to pick up your marked coursework from you tutorial and clarify issues with your submission. Failure to address those may cause you to loose marks.
Solutions will be made available shortly after the deadline. There are going to be 8 sets of problems: the best 5 count for a total of 25% of the module mark. Thus you can miss three deadlines without any ill effect, and failing to hand in a few pieces of coursework due to (for example) short periods of illness are to be handled through this mechanism as opposed to the formal Extenuating Circumstances route. However! You should always log Extenuating Circumstances along with supporting evidence if you are ill as the duration and full impact of any illness obviously cannot be known from the outset.
Solutions will be provided shortly after the deadlines — consequently there is no late hand-in option for the coursework.
Marks (anonymous, sorted by student ID) will be released once each coursework has been marked. The marks are preliminary, subject to change, and only given in the interest of providing quick, individual feedback: no marks are ever definitive until they have been formally approved by the School's Board of Examiners.
For assistance with the coursework, please see the G52MAL Coursework Support Page, or visit the G52MAL Web Forum.
Some of the coursework exercises will make use of Haskell. If your Haskell is rusty, you may want to work through the following set of (unassessed) Haskell exercises first:
There is a School Web Forum for G52MAL. It's accessible via the School of Computer Science intranet by clicking on School Forum to the left. After having logged in, select Teaching, and then G52MAL. Or follow this direct link.
The forum is intended for asking questions about and discussing aspects of G52MAL, such as the coursework. It will be monitored by the G52MAL team, and we'll endeavour to answer any outstanding questions reasonably quickly. However, any one is free to contribute to the discussions and help with answering questions. Indeed, in the spirit of an on-line forum, you are encouraged to do so!
Of course, we do ask that you do not post the exact solutions to the coursework! The point of the coursework is that you should ultimately solve the problems yourselves so that you know what you have understood and what you need to work more on or ask about.
There is a Coursework Support Page for G52MAL, which contains a collection of frequently asked questions, common mistakes, and general coursework tips.
This should be your first port of call when seeking coursework help.
Some basic information about the exam:
Past exam papers can be found by logging in to the Portal and searching for G52MAL in the Exam Papers library search, under the Library tab.