Lectures
Because of the
coronavirus situation, all teaching on the course has moved to the Zoom
remote meeting platform. For further information, see Forums -> Announcements.
- FileIntroduction and practical arrangements FilePDF document
- FileIntroduction handout FilePDF document
What is theoretical computer science? Sets. Relations and functions. Equivalence relations. Proof by induction. Automata, alphabets, strings, languages.
- FileLecture 1 handout FilePDF document
- FileLecture 2. Finite automata FilePDF document
State diagrams and transition tables. Programming with finite automata. Formal definition of finite automata. Excursion: Extensions of finite automata.
- FileLecture 2 handout FilePDF document
Minimisation of finite automata. Nondeterministic finite automata. Equivalence of deterministic and nondeterministic finite automata.
- FileLecture 3 handout FilePDF document
- FileLecture 4. Regular expressions FilePDF document
Syntax and semantics of regular expressions. Regular expressions and finite automata. Excursion: Regular expressions in programming languages.
- FileLecture 4 handout FilePDF document
- FileLecture 5. Limitations of regular languages; context-free grammars and languages FilePDF document
The pumping lemma. Generating strings with grammars. Context-free grammars. Some useful constructions. Right- and left-linear grammars.
- FileLecture 5 handout FilePDF document
The parsing problem and parse trees. Recursive-descent parsing. LL(1) grammars. Excursion: Attribute grammars. Excursion: Parsing tools in the Scala language. Supplement: General definition of LL(1) grammars.
- FileLecture 6 handout FilePDF document
Parsing context-free grammars. The Chomsky normal form for CFGs. The CYK parsing algorithm. Pushdown automata. Pushdown automata and context-free languages. A pumping lemma for context-free languages.
- FileLecture 7 handout FilePDF document
- FileLecture 8. Turing machines FilePDF document
Turing machines. Extensions of Turing machines: multitrack machines, multitape machines, nondeterministic machines. Some computability theory: Turing-recognisable and Turing-decidable languages. Excursion: The halting problem, first encounter.
- FileLecture 8 handout FilePDF document
- FileLecture 9. Decidability and undecidability FilePDF document
Decidable and semi-decidable languages and problems. Background: countable and uncountable sets. Universal Turing machines and undecidable problems.
- FileLecture 9 handout FilePDF document
- FileLecture 10. More on undecidability FilePDF document
Undecidability of some Turing machine properties: the halting and non-emptiness problems. Other undecidability results: logic and algebra, Post's correspondence problem, the Chomsky hierarchy. Computable functions and reductions. Excursion: Post's correspondence problem.
- FileLecture 10 handout FilePDF document
Rice's theorem. Unrestricted grammars and their relation to Turing machines. Context-sensitive grammars. A glimpse beyond: Computational complexity.
- FileLecture 11 handout FilePDF document
Programs as state transformers. Specification and correctness of programs: weak and strong correctness, proving weak correctness viar loop invariants. Establishing strong correctness.
- FileLecture 12 handout FilePDF document