G52MAL Lecture Note Index

Autumn 2008

This page will contain links to lecture notes for the lectures. Additionally, all electronic material used during the lectures, in particular slides and any major pieces of code will be available via this page. The slides are all in PDF, and there are three versions available for each lecture. The basic version is intended for on-screen viewing only, whereas the 4 up and 9 up versions are mainly intended for printing, putting 4 and 9 slides respectively on each page.

Lecture 1: Administrative Details and Introduction

29 September 2008


Lecture 17: Recursive-Descent Parsing: Introduction

27 November 2008


Lecture 18: Recursive-Descent Parsing: Elimination of Left Recursion

1 December 2008


Lecture 19: Recursive-Descent Parsing: Predictive Parsing

4 December 2008


Lecture 20: Turing Machines and Decidability

8 December 2008

The Turing Machine simulator used in the lecture is availble here. It's a Java applet so a Java runtime environment needs to be installed to use it. The source code for the applet is also available via the website, so it is posisble to run the simulator locally.

The following Turing Machine program for recognising words a^nb^nc^n where n >= 1 was developed by Thorsten Altenkirch It is simpler than the one in the lecture notes. The notation is slightly different from that used in the lecture: the first two fields gives the current state and the current tape symbol, the next three gives the new state, the tape symbol to replace the current type symbol by, and whether to move the read/write head left (<) or right (>). An underscore (_) is used as the blank symbol. As this particular simulator does not have any designated accepting states, we take the machine stopping in a configuration with a "Y" as the only non-blank symbol on the tape to mean success, and the machine stopping in any other configuration to mean reject.

1,a,2,#,>
2,a,2,a,>
2,#,2,#,>
2,b,3,#,>
3,b,3,b,>
3,#,3,#,>
3,c,4,#,<
4,#,4,#,<
4,b,4,b,<
4,a,5,a,<
4,_,6,_,>
5,a,5,a,<
5,#,1,#,>
6,#,6,_,>
6,_,7,_,>
7,_,8,Y,>
Be aware that there might be a slight problem with the end of line character when pasting the code into the applet.


Last updated 8 December 2008.