Teaching: CS2121

COMP20121: The Implementation and Power of Computer Languages

(Semester 1)

I used to teach this course when it was known as CS2121. The notes I wrote then are still in use, which is why this webpage still exists.


Course notes

I appreciate any feedback on the notes. For this purpose please email me at A.Schalk at cs.man.ac.uk.

The exercises are at the end of each section. The last pages of Sections 1, 2 and 3 contain the assessed exercises. Assessment will occur in the, where it will also be possible to ask questions regarding the non-assessed exercises.

Section 1: Regular Languages and Finite Automata. gzipped postscript version, pdf version.

Section 2: Context-free Grammars and Pushdown Automata. gzipped postscript version, pdf version.

Section 3: Turing machines gzipped postscript version, pdf version.

Section 4: Computability gzipped postscript version, pdf version.


Content (of the theoretical part)

Official Syllabus for CS2121, The Implementation and Power of Computer Languages.

The theoretical part of this course-unit is concerned with the theory underlying the principles that were introduced in the first part of the course, where you learned about parsing programs and regular expressions, among other things. It is also the part that concerns itself with the power of computer languages in that it addresses the question of whether there are problems whose answer is not computable for some intrinsic reason.

When learning about regular expressions and other syntactical devices you might find these somewhat unwieldy to deal with, and writing a parser for these may have seemed a rather difficult task. In this part of the course-unit we will study theoretical constructs that help with such jobs, so called automata. These have the advantage that they can be presented pictorially. While machines typically deal very well with syntax there are many situations where humans do much better when the information is provided in form of a picture. We will learn which automata correspond to regular expressions, and what has to be changed if we want to deal with more complex languages, resulting in the Chomsky-hierarchy.

One particular kind of automaton are so-called Turing machines named after the British mathematician and computer scientist Alan Turing who did ground-breaking work in the theory of computability. Turing was an eminent British logician who eventually accepted a position here in Manchester in the maths department, and you will find his picture around this building. He started with a simple idea. Take a function f that takes a natural number as an input and gives a natural number as an output. When is this function something that can be computed? This work was started in the thirties when computers did not yet exist, so Turing used the idea of a human carrying out the computations---a human who would mechanically follow instructions, that is, carrying out an algorithm or program. It turned out that this notion of computability is much more general than originally perceived, and we can use extensions of the arguments used by Turing to argue about what can be computed in languages such as ML, C, Java, or various assembler languages. The surprising answer is that it does not matter which language is used. The question of what kind of problems are intrinsically uncomputable will occupy us in the last part of this course.


Learning the material

There are four components that will help you to learn the material of my part of the course unit. There are the lectures, lecture notes, text books and examples classes. The notes aim to give you a summary of the examinable material. Any text book (see the references) will provide a much more detailed account of this area, often going beyond what is taught in the course, and providing many more examples. But a text book, by definition, is a static medium, and some things are much better explained dynamically. In the lectures I can point at things, emphasize important issues, react to questions, repeat explanations in a different way, simulate processes dynamically. You can get none of these things out of even the best text book. The practical component of this part of the course consists of a number of exercises strewn throughout the notes. Ideally after one lecture (and before the next) you would (re)read the notes that were covered, and tackle all the exercises in that section.


26 September 2006