COMP 218 course materials and details; Semester 2 2011/12

Department's COMP218 web page, includes brief description and recommended text.

COMP218 lectures:

Ongoing Turing tape competition hosted at Uni of Nottingham; continues through to mid-September

Class tests and exams

There are two class tests that are set during COMP218. Each test is worth 10 per cent of the total credit for the module, and the exam accounts for the remaining 80 per cent. For the purpose of passing the module, there are no constraints on how the marks obtained are divided amongst the class tests and the exam.

You should attempt the questions on the following, before looking at the solutions!
Exams

Tests

Notes

Slides

General overview

First lecture: general introduction to COMP218.

First three weeks of lectures: Regular languages — these are languages that may be described using finite automata or alternatively using regular expressions.

Afterwards: context-free grammars, and the languages that they can define. Then move on to recursive and recursively-enumerable languages.

Recent lectures

I will add summaries of lectures to a list here, as I give them.
  • 27.4.12. Last lecture, on usage of reductions to establish that various language-recognition problems are undecidable.
  • 24.4.12. Undecidability of the Halting Problem.
  • 23.4.12. Universal Turing machines; the language Lhalt, which we shall see is undecidable.
  • 16.4.12. Intro to Turing machines, with examples to give an idea of how to construct a TM that accepts a given language.
  • 23.3.12. Cancelled (was to be class test 2, see above)
  • 20.3.12. LL(1) parser generation; completes “lecture11” slides
  • 19.3.12. Introduction to LL(1) parse tables
  • 16.3.12. Pumping Lemma for context-free languages
  • 13.3.12. Conversion from PDA to CFG. Also, we worked through the problem of how to prove that a CFG for the language a*b*c* needs at least 2 variable symbols.
Check syntax of email address using Javascript's regular expressions.
Paul Goldberg