COMP2012/G52LAC Languages and Computation

Spring 2019

Corrected model solutions for third set of coursework problems released!

Literature Lectures Lecture Links
Coursework Forum
Examination References



Typeset lecture notes [ACN19] (PDF), which includes exercises with model answers, supports the lectures, along with electronic lecture slides [ELS19] for some of the lectures.

Please note that you should not expect these notes to be a complete record of all that is said and discussed during the lectures. Lecture attendance is compulsory, and reading the main references strongly encouraged. That said, the typeset lecture notes are fairly comprehensive.

The book Introduction to Automata Theory, Languages, and Computation, 3rd edition [HMU3] 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 and third editions, 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 [Lin6] by Peter Linz can be used as an alternative or complement to [HMU3]. The picture shows the sixth edition. Earlier 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 [ACN19] 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 COMP3012/G53CMP 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#DateContentLctr Reading
1 31 Jan Administrative Details and Introduction nhn & vxc [ELS19, Le 1; ACN19, Sec. 1–2; HMU3, Ch. 1]
2 31 Jan Deterministic Finite Automata (DFA) nhn [ACN19, Sec. 3, 3.1; HMU3, Ch. 2, 2.1–2.2]
3 7 Feb Nondeterministic Finite Automata (NFA) nhn [ELS19, Le3; ACN19, Sec. 3, 3.2–3.2.2; HMU3, 2.3–2.3.4]
4 7 Feb Equivalence between NFA and DFA nhn [ELS19, Le 4; ACN19, Sec. 3, 3.2.3; HMU3, 2.3.5–2.4]
5 14 Feb Regular Expressions vxc [ELS19, Le 5; ACN19, Sec. 4, 4.1–4.2; HMU3, Ch.3, 3.1, 3.3]
6 14 Feb Equivalence between Regular Expressions and Finite Automata vxc [ELS19, Le 6; ACN19, Sec. 4, 4.3–4.4; HMU3, 3.2.3]
7 21 Feb Proving Languages not to be Regular vxc [ELS19, Le 7; ACN19, Sec. 6; HMU3, Ch.4, 4.1, 4.2 (only intro)]
8 21 Feb Introduction to Context-Free Grammars (CFG) vxc [ELS19, Le 8; ACN19, Sec. 7, 7.1, 7.6; HMU3, Ch.5, 5.1–5.1.4, 5.3]
9 28 Feb The Language of a CFG nhn [ELS19, Le 9; ACN19, Sec.7, 7.2–7.3; HMU3, 5.1.5–5.1.7]
10 28 Feb Derivation Trees and Ambiguity nhn [ELS19, Le 10; ACN19, Sec. 7, 7.4–7.5; HMU3, 5.2, 5.4–5.4.1, 5.1.4, 5.4.3–5.4.5]
11 7 Mar Disambiguating Context-Free Grammars nhn [ELS19, Le 11; ACN19, Sec. 7, 7.5, Sec. 8, 8.1, 8.5; HMU3, 5.4.2]
12 7 Mar Recursive-Descent Parsing: Introduction nhn [ELS19, Le 12; ACN19, Sec. 10, 10.1–10.4; HMU3, 5.3.1-5.3.2]
13 14 Mar Recursive-Descent Parsing: Elimination of Left Recursion nhn [ELS19, Le 13; ACN19 Sec. 10.5, 8.1–8.3, 8.6]
14 14 Mar Recursive-Descent Parsing: Predictive Parsing nhn [ELS19, Le 14; ACN19 pp. Sec. 10.6–10.7, 8.2, 8.4]
15 21 Mar Turing Machines vxc [ELS19, Le 15; ACN19, Sec. 11, 11.1–11.2; HMU3, Ch.8, 8.2]
16 21 Mar λ-Calculus vxc [ELS19, Le 16; ACN19, Sec. 12, 12.1–12.5]
17 28 Mar The Church-Turing Thesis vxc [ELS19, Le 17; ACN19, Sec. 12.6; HMU3, 8.2.1; Lin6, Ch.13 only intro]
18 28 Mar Decidability and the Halting Problem vxc [ELS19, Le 18; ACN19, Sec. 11.3–11.5; HMU3, Ch.9; Lin6, Ch.12]
19 4 April Computational Complexity and the P vs. NP Problem vxc [ELS19, Le 19; ACN19, Sec.13, 13.1–13.3; HMU3, Ch.10; Lin6, Ch.13–14]
20 4 April Catch up/Discussion (TBD)
-- 11 Apr NO LECTURE
-- 11 Apr 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 or by following the per-lecture links above.


The coursework consists of three problem sets. The average of the best two 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–7) 20 Feb 27 Feb
2 (for lect. 8–14) 13 Mar 20 Mar
3 (for lect. 15–19) 3 Apr 12 Apr

The deadline for submitting solutions is 3 PM on the submission date. Solutions are to be submitted to the Student Service Centre as handwritten (recommended) or typeset hard copies. The procedure for hard copy submission is explained on the Student Services' Coursework Submission page. This page also provides a link to the standard cover sheet that should be used. Model solutions will normally be released shortly after the deadline. Marks will be released through Moodle and marked solutions will be returned via the Student Service Centre.

To make quick marking and feedback possible, and as model solutions will be released shortly after the submission deadline, late submissions will not be considered. Extenuating circumstances affecting a single problem set are addressed by the rule that only the two best solutions count. In case of valid extenuating circumstances affecting two or more of the problem sets, suitable arrangements will be made.

Problem sets below. Model solutions will be added shortly after the deadlines.

COMP2012/G52LAC Moodle Forum

A Moodle Forum for COMP2012/G52LAC has been set up.

The forum is intended for asking questions about and discussing aspects of COMP2012/G52LAC, like the coursework. It will be monitored by the COMP2012/G52LAC 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.


Some basic information about the exam:

In the case of a resit examination:

The style of the exam will be similar to two past exams below. These revision notes give more detail on what to revise and some suggestions regarding how to prepare for the exam.

Model solutions for the above past exams:


Last updated 8 May 2019.