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

department FCS web page (some past exam papers)

**Lectures:**
5:00pm on Mondays and Wednesdays, 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 | Giulio Guerrieri | room 051 (check this) | Tuesday 9am note change, weeks 3–8 |

2 | Paul Goldberg | room 051 | Thursday 5pm note change, weeks 3–8 |

**Hand in exercises** by 12 noon on the preceding Friday in the
marker’s pigeon hole.

**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 2 | Slides for 4-5 lectures (context-free languages; Turing machines, recursive languages) Lecture 18.10.17: recap of 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 9.10.17: general overview and introduction to finite automata. Lecture 11.10.17: 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 16.10.17: conversion of finite automaton to equivalent regular expression (see Chapter 1.3 of textbook), introduction to Pumping Lemma (Chapter 1.4 of textbook) |

Proofs: what is required, and getting started.

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