COM2003 - Automata, Logic and Computation
(First Semester)
Lectures
- 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 nonregular 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] [corrected PDF of page 2]
- 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]
- Lecture 18 - Some further complexity classes: NP-Hard problems, PSPACE and Savitch's Theorem (Sipser pp. 302 & 307-313) [PDF]
Study Guides (authored by Tom Cassey and Tom Hinton, University of Bristol)
Problems Sheets
Exam Guide
Exam Revision Guide
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 10:00 to 11:00,
when a lecture is not taking place in that slot. 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
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.
Just for Fun