G52MAL Machines and Their Languages (UNMC)

Spring 2011

Spring 2011: This page is for G52MAL at our Malaysia Campus (UNMC). G52MAL Nottingham is being taught by Neil Sculthorpe, pages here.

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 [ELS07] 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. The earlier third edition should work too. And a fifth edition is just out (February 2011). 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. Also note that the lecture numbers reflect one-hour long lectures. Two of these will be given in each two-hour lecture slot.

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

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


Coursework

After discussions between the module conveners, the coursework setup has been changed a little vith a view to maximise their effectiveness. There are now two parts to the coursework:

One or two sets of problems are to be completed weekly and handed in before the deadline, Monday 4 PM the following week. Solutions will be made available shortly after the deadline. There are going to be around 8 sets of problems; the best 3 counts for a total of 10 % of the overall mark. Thus you can miss two or three deadlines without any ill effect, and failing to hand in a few pieces of coursework due to e.g. 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.

Additionally, there are going to be two unseen, written, in-class tests comprising a selection of problems similar to those of the problem sets that have been completed so far. Each test is worth 7.5 % of the overall mark, for a total of 15 %.

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

Caution! 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.


Examination

Some basic information about the exam:

The style of the exam will be similar to the ones that have been given for G52MAL at the Nottingham campus over the past few years. Past examination papers can be found here.

Answers to the January 2009 Nottingham exam can be found here.


References


Last updated 8 May 2011.