G52MAL Lecture Note Index (UNMC)

Spring 2011

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

16 February 2011

Lecture 3: Nondeterministic Finite Automata (NFA)

22 February 2011

Lecture 7: Equivalence of Regular Expression and Finite Automata

1 March 2011

Lecture 17: Recursive-Descent Parsing: Introduction

16 March 2011

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

16 March 2011

Lecture 19: Recursive-Descent Parsing: Predictive Parsing

22 March 2011

Lecture 20: Turing Machines and Decidability

22 March 2011

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.

Be aware that there might be a slight problem with the end of line character when pasting the code into the applet.

Last updated 23 March 2011.