COM2003 - Automata, Logic and Computation (First Semester)
Lectures
- Lecture 0 - (pre-lecture reading) Sipser chapter 0
- Lecture 1 - An introduction to the course, and the subject. Applications of abstract computational models in real computing systems. Introduction to deterministic finite automata (DFAs) and regular languages (Sipser pp. 31-43) - [PDF]
- Lecture 2 - More DFA examples. Regular operations and closure properties. Closure under union (Sipser pp. 44-47) - [PDF]
- Lecture 3 - Introduction to nondeterministic finite automata (NFAs). Closure under concatenation (Sipser pp. 47-53) - [PDF]
- Lecture 4 - Formal definition of computation by NFAs. Equivalence of DFAs and NFAs. Closure under union and star operators (Sipser pp. 54-62) - [PDF]
- Lecture 5 - Formal definition of regular expressions, notation, identities and examples. Construction of an NFA to recognise the language described by a regular expression (Sipser pp. 63-69) - [PDF]
- Lecture 6 - Formal definition of generalised nondeterministic finite automata (GNFAs). Construction of a GNFA for a language and its reduction to the regular expression describing that language (Sipser pp. 69-76) - [PDF]
- Lecture 7 - Nonregular languages. The pumping lemma for regular languages (Sipser pp. 77-82) - [PDF]
- Lecture 8 - Formal definition of context-free grammars and context-free languages (CFGs and CFLs). Examples of CFGs. Relationship of CFLs to the regular languages (Sipser pp. 101-107) - [PDF]
- Lecture 9 - Ambiguous derivations, CFGs and CFLs. Chomsky Normal Form for CFGs (Sipser pp. 107-110) - [PDF]
- Lecture 10 - Introduction to pushdown automata (PDAs) (Sipser pp. 111-116) - [PDF]
- Lecture 11 - Pushdown automata and context-free languages (Sipser pp. 117-125) - [PDF Scanned]
- Lecture 12 - Non-context-free languages and the pumping lemma for CFLs (Sipser pp. 125-129) - [PDF]
- Lecture 13 - Introduction to Turing Machines (Sipser pp. 139-147) - [PDF]
- Lecture 14 - Turing Machine variants, equivalence, decidability (Sipser pp. 150-156 & 168-172) - [PDF]
- Lecture 15 - Undecidability and the Halting Problem, countability and uncountability, unrecognisability (Sipser pp. 167 & 175-184) - [PDF]
- Lecture 16 - Computational complexity, P and NP (Sipser pp. 251-272) - [PDF]
- Lecture 17 - P vs NP, Reductions, NP-Completeness, Bandersnatches (Sipser pp. 273-287 & 290-294) - [PDF]
Problems Sheets
Throughout the course you should be tackling problems and exercises from Sipser, to develop your understanding of concepts covered in the lectures and the associated reading from the book. While these cannot be formally marked, you are encouraged to bring full or partial solutions to the office hour for feedback, especially if you are uncertain about whether your solutions are correct.
In addition, two formative assessments will be set. These are not credit bearing, but are an opportunity for you to receive detailed feedback on your understanding of the core concepts and techniques that will be required for the exam.
Exam Guide
Assessment for semester 1 will be entirely by examination in January.
Office Hour
James' main office is not in Regent Court. Hence he will hold an office hour on Fridays in his departmental office (152), from 12:00 to 13:00. Please contact James in person about the course either after one of the lectures, or during this office hour. Please do not use email except in case of urgency - you are likely to be told to come to an office hour.
Staff Absences
Due to research commitments, lectures and office hours will not be held on the following dates:
- Friday 10th October
- Monday 13th October
- Monday 17th November
- Friday 5th December
- Monday 8th December
- Friday 19th December (office hour only; lectures finishing early for Christmas)
Learning Aids
You may find it useful to use a simulation environment to develop and veryify your understanding of automata and computation, such as JFLAP from Duke University. Note that this software will not be directly used or supported during the course, but is suggested for self-study. Also note that you must learn the procedures for manipulating automata covered during the course, rather than simply rely on JFLAP to do them for you; you will not be able to use JFLAP during the exam!
Core Text
The lectures and study material closely follow the contents of M. Sipser, Introduction to the Theory of Computation (2nd edition), available from the library and from Blackwell's. You are expected to read the pages indicated for each lecture.
Just for Fun
James A. R. Marshall. Last modified on December 17th 2014