This page is maintained by Paul Goldberg, teaching FCS in Michaelmas term 2016–17; please re-visit this page since it is updated regularly.

department FCS web page (some past exam papers)

**Lectures:**
4:00pm on Mondays and Fridays, Lecture theatre A, weeks 1 to 8
(official timetable)

**Office hours:** I will usually be free to talk after lectures.

**Classes:**
Problem-based exercise classes in weeks 3–8.

Group | tutor/marker | place | time |

1 | Enrico Marchioni | room 441 | Friday 9am, weeks 3–8 |

2 | Aris Filos-Ratsikas | room 441 | Friday 10am, weeks 3–8 |

**Hand in exercises** by 5:30pm on the preceding Tuesday in the
marker’s pigeon hole or by email.

**Textbook:** *Introduction to the Theory of Computation* 2nd Edition by Mike Sipser. There are other books that cover all/most of the material in this course, e.g. *Models of Computation: exploring the Power of Computing* by John E. Savage; *Introduction to Automata Theory, Languages and Computation* by Hopcroft, Motwani, and Ullman; *An Introduction to Formal Languages and Automata* by Linz; *Computational Complexity* by Papadimitriou.

slides 5 |
intro to predicate logic, and computational aspects 28.11.16: got as far as Trakhtenbrot’s theorem. 2.12.16: more details of proof of Trakhtenbrot’s theorem, other undecidability results. |

slides 4 |
Computational complexity (about 4 lectures) 14.11.16: introduction to the complexity classes P and NP.
Polynomial-time reducibility, and we noted the analogy with
reductions in the context of proofs of undecidability.
The concept of problems that are 18.11.16: propositional logic and Cook’s theorom. 21.11.16: Polynomial-time reductions, e.g. reduction from LATIN SQUARE COMPLETION to SUDOKU |

slides 3 |
Undecidability (about 2 lectures) lecture 7.11.16: undecidability of the Halting Problem; reductions, and how we can use pre-existing undecidability results to obtain new ones. |

slides 2 | Slides for 4-5 lectures (context-free languages; Turing machines, recursive languages) Lecture 31.10.16: operation of TMs; deciding versus accepting; Church-Turing thesis (textbook Chapter 3) Lecture 28.10.16: Pumping lemma for CFLs; Turing machines. TM example another TM example (examples are useful, but are missing from the slides themselves). Examples of TMs in textbook, pp.142–147 Lecture 21.10.16: get started on equivalence of PDAs and CFGs. (chapter 2.2 of textbook; this result is similar to Kleene’s theorem, showing that 2 different language representations have the same expressive power.) 24.10.16: equivalence of PDAs and CFGs. Lecture 17.10.16: introduction to pumping lemma and examples. (Exercise: construct a non-regular (formal) language for which the pumping lemma |

slides 1 | Slides for first 2-3 lectures; textbook chapter 0, 1.1; examples on p38 onwards may be helpful. Lecture 10.10.16: general overview and introduction to finite automata. Lecture 14.10.16: reached slide 42; see textbook p44: the operations union, concatenation, and star; see textbook chapter 1.2: Nondeterminism, NFA examples p51 onwards; p55: general idea of proof that every NFA has an equivalent DFA; p59 onwards: detailed proofs of closure properties Lecture 17.10.16: conversion of finte automaton to equivalent regular expression (see Chapter 1.3 of textbook), introduction to Pumping Lemma (Chapter 1.4 of textbook) |

- Exercises 6 for classes in week 8
- Exercises 5 for classes in week 7
- Exercises 4 for classes in week 6
- Exercises 3 for classes in week 5
- Exercises 2 for classes in week 4
- Exercises 1 for classes in week 3

Proofs: what is required, and getting started.

sample proof (of the “union” construction (many other detailed proofs can be found in the textbook)