COM2030 Machines and Languages

2003-2004 Autumn Semester - Half Module - 10 Credits

Note: details may differ in some places from those given in the handbook or on the departmental Web pages for this course. The information given here should be taken to be correct. The lecturer reserves the right to vary the course contents at the time of delivery.

Teaching Method

The lecturer is Dr Matt Fairtlough. Please note spelling!

Reading weeks will be in weeks 9 and 10 of the semester.

As well as the formal lectures there will be 8 or 9 tutorial and/or laboratory sessions to support the practical exercises. Tutorials begin in week 2.

Summary

This half-module tries to answer the questions: "what is computation?" and "how can computing machines be characterised and classified?". By introducing a series of abstract models of computing machines, it will explore the capabilities and limitations of digital computers. It will develop skills in modeling and reasoning about discrete systems, applying some of the ideas developed in the Discrete Foundations course. In particular, it will investigate simple finite state automata, pushdown automata and Turing machines and study their relation to classes of formal languages (the Chomsky hierarchy). It will also consider recursive function theory and its relation to automata theory (the Church-Turing thesis) and (if time permits) introduce the study of computational complexity.

Lecture notes

Lecture 1 (pdf) Introduction to course; deterministic finite automata
Lecture 2 (pdf) DFAs as language acceptors; regular languages; non-deterministic finite automata
Lecture 3 (pdf) Introduction to formal grammars; equivalence of regular grammars and finite automata
Lecture 4 (pdf) Regular expressions
Lecture 5 (pdf) Introduction to pushdown automata
Lecture 6 (pdf) Pushdown automata and context-free grammars
Lecture 7 (pdf) The pumping lemma and the limits of context-free languages
Lecture 8 (pdf) Deterministic PDAs; LL(k) and LR(k) parsing
Lecture 9 (pdf) Introduction to Turing machines
Lecture 10 (pdf) Modular construction of TMs
Lecture 11 (pdf) Turing machines as language acceptors
Lecture 12 (pdf) Coding schemes for Turing machines; universal Turing machines; the halting problem
Lecture 13 (pdf) Introduction to recursive function theory
Lecture 14 (pdf) More on primitive recursion and partial recursion
Lecture 15 (pdf) The Church-Turing thesis
Lecture 16 (pdf) A minimal programming language

Exercise sheets

Sheet 1 (pdf) and solutions
Sheet 2 (pdf) and solutions
Sheet 3 (pdf) and solutions
Sheet 4 (pdf) and solutions

Exam revision

1999-2000 exam paper (pdf) (ps)
Solutions to above (pdf) (ps)

Other resources

There is a good tool JFLAP for designing and simulating grammars and automata which may be found among other tools on Susan Rodger's website. You can download the jar file and/or the sources; it requires Java 1.3.1 or later. There is also an applet version if you want to try out the software before downloading it. Here is the jar file. I have written some simple Haskell code implementing partial recursive functions as functions over lists.

Matt Fairtlough

Last modified: Tue Dec 23 14:54:07 GMT 2003