G52MAL Machines and Their Languages

Spring 2016

Model solutions for the May 2016 examination now available!

Overview
Literature Lectures Lecture Links
Coursework Forum
Examination References

Overview


Literature

A set of lecture notes [AN07] (PDF), originally developed by Dr. Thorsten Altenkirch and then updated and adapted, support the lectures, along with electronic lecture slides [ELS16] 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 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.

There is now also a third edition of this book. This is fine too. However, the page references below are for the second edition.

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.

The book An Introduction to Formal Languages and Automata [Lin06] by Peter Linz can be used as an alternative or complement to [HMU01]. The picture shows the fourth edition. Later editions should work too. In fact, as the lectures cover standard material, but without following any specific book very closely, there are a range of possible text books for the student who wish to delve deeper into the subject than what the lectures notes [AN07] do.

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.


Lectures

The lecture overview below is at present tentative. For example, topics may change a bit, especially towards the end, or the schedule might slip.

Lecture#DateContentReading
1 26 Jan Administrative Details and Introduction [ELS16, Le 1; AN07, pp. 1--6; HMU01, ch. 1]
2 28 Jan Deterministic Finite Automata (DFA) [AN07, pp. 7--8; HMU01, pp. 37--54]
3 2 Feb Nondeterministic Finite Automata (NFA) [ELS16, Le3; AN07, pp. 9--11; HMU01, pp. 55--59]
4 4 Feb Equivalence between NFA and DFA [ELS16, Le 4; AN07, pp. 11--13; HMU01, pp. 60--72]
5 9 Feb Regular Expressions [ELS16, Le 5; AN07, pp. 13--17; HMU01, pp. 83--89, 108--113]
6 11 Feb Equivalence between Regular Expressions and Finite Automata [ELS16, Le 6; AN07, pp. 17--25; HMU01, pp. 101--105]
7 16 Feb Minimization of Finite Automata [ELS16, Le 7; AN07, pp. 25--29; HMU01, pp. 154--164]
8 18 Feb Proving Languages not to be Regular [ELS16, Le 8; AN07, pp. 29--31; HMU01, pp. 126--131]
9 23 Feb Introduction to Context-Free Grammars (CFG) [ELS16, Le 9; AN07, pp. 21--33; HMU01, pp. 169--177, 191--205]
10 25 Feb The Language of a CFG [ELS16, Le 10; AN07, pp. 33--35; HMU01, pp. 177--181]
11 1 Mar Derivation Trees and Ambiguity [ELS16, Le 11; AN07, pp. 35--37; HMU01, pp. 181--191, 205--207, 175-177, 211--214]
12 3 Mar Disambiguating Context-Free Grammars [ELS16, Le 12; AN07, pp. 35--37; HMU01, pp. 207--211]
13 8 Mar Pushdown Automata (PDA) [ELS16, Le 13; AN07, pp. 37--40; HMU01, ch. 6]
14 10 Mar The Language of a PDA [ELS16, Le 14; AN07, pp. 40--41; HMU01, ch. 6]
15 15 Mar Recursive-Descent Parsing: Introduction [ELS16, Le 15; AN07, pp. 41--43; HMU01, ch. 6. pp. 192--195]
16 17 Mar Recursive-Descent Parsing: Elimination of Left Recursion [ELS16, Le 16; AN07 pp. 44--49]
17 19 Apr Recursive-Descent Parsing: Predictive Parsing [ELS16, Le 17; AN07 pp. 44--49]
18 21 Apr Turing Machines and Decidability [ELS16, Le 18+19; AN07, pp. 49--56; HMU01, ch. 8 & 9]
19 26 Apr Turing Machines and Decidability (cont.) [ELS16, Le 18+19; AN07, pp. 49--56; HMU01, ch. 8 & 9]
20 28 Apr NO LECTURE
21 3 May NO LECTURE
22 5 May NO LECTURE


Lecture Links

Copies of electronic slides, any major pieces of program code, other electronic material used during the lectures, and useful links can be found here.


Coursework

The coursework consists of four problem sets. The average of the best three counts for 25 % of the overall mark for the module. The issue and submission dates are as follows:

Problem Set#Issue DateSubmission Date
1 (for lect. 1–2) 29 Jan 5 Feb
2 (for lect. 3–6) 12 Feb 19 Feb
3 (for lect. 7–10) 26 Feb 4 Mar
4 (for lect. 11–14) 11 Mar 16 Mar (Wednesday!)
Additionally, an unassessed set, covering the material of lectures 15–20, is planned for after the Easter break.

The deadline for submitting solutions is 4 PM on the submission date. Solutions are to be submitted to the School office as handwritten (recommended) or typeset hard copies. Model solutions will normally be released shortly after the deadline. For that reason, and to make quick marking and feedback possible, late submission will not be considered. Extenuating circumstances affecting a single problem set are addressed by the rule that only the three best solutions count. In case of extenuating circumstances affecting two or more of the problem sets, suitable arrangements will be made.

Problem sets below. Solutions will be added shortly after the deadlines.


G52MAL Moodle Forum

A Moodle Forum for G52MAL has been set up.

The forum is intended for asking questions about and discussing aspects of G52MAL, like 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.


Examination

Some basic information about the exam:

In the case of a resit examination:

The style of the exam will be similar to the ones given over the past few years, such as the ones below. However, note that there is not going to be any choice regarding which questions to answer: all questions will be compulsory. (This is unlike what was the case in some of the older exams below.)

Model solutions for some past exams:


References


Last updated 6 June 2016.