# 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.*