Lectures:Mondays 13:15--15:00 in HA2 and Tuesdays 10:00--11:45 in HC3.

Extra lectureThursday 10:00-11:45 in HA3.onlythe first week:

Exercise sessions:Thursdays 13:15--15:00 in EB.See link at Time Edit for details.

Lectures Monday 21/3 Slides Organisation and overview of the course Tuesday 22/3 Slides Formal proofs, inductively defined sets, proofs by (structural) induction

Sections 1.2--1.4 in the bookThursday 23/3 Slides Central concepts of automata theory, DFA

Sections 1.5, 2--2.2Exercises Thursday 24/3 Text Formal proofs, alphabets and words Assignment Deadline: Thursday 31/3Text Formal proofs

Lectures Monday 28/3 Slides DFA, NFA, subset construction algorithm

Sections 2.3--2.3.5Tuesday 29/3 Slides Equivalence between DFA and NFA, NFA with epsilon transitions

Sections 2.3.5--2.5.3Exercises Thursday 31/3 Text DFA. NFA, NFA with epsilon transitions

Some exercises should be done in week 3.Assignment Deadline: Thursday 7/4Text DFA and NFA

Lectures Monday 4/4 Slides NFA with epsilon transitions, regular expressions

Sections 2.5.4--2.5.5, 3--3.2.1, 3.4Tuesday 5/4 Slides Equivalence between AF and RE, Pumping Lemma for RL

Sections 3.2.2--3.2.3, 4--4.1Exercises Thursday 7/4 Text Regular expressions

Some exercises should be done in week 4.Assignment Deadline: Thursday 14/4Text Epsilon-NFA, RE

Lectures Monday 11/4 Slides Closure and decision properties of regular languages

Sections 4.2--4.3Tuesday 12/4 Slides Equivalence of RL, minimisation of automata

Section 4.4Exercises Thursday 14/4 Text Properties of RL, minimisation of automata Assignment Deadline: Thursday 5/5Text Regular languages

Lectures Monday 2/5 Slides Context free grammars, derivations, parse trees

Sections 5--5.2Tuesday 3/5 Slides Ambiguous grammars, Chomsky hierarchy

Section 5.4Thursday 5/5 10-12 ES51 Extra consultation class, please come with questions to discuss!! Exercises Thursday 5/5 Text Context free grammars Assignment Deadline: Thursday 12/5Text Context free grammars

Lectures Monday 9/5 Slides Normal forms and Pumping lemma for CFG

Section 7--7.2Tuesday 10/5 Slides Properties of CFG

Sections 7.3--7.4Exercises Thursday 12/5 Text Context free languages Assignment Deadline: Thursday 19/5Text Context free languages

Exercises Monday 16/5 Exams

SolutionsSolving old exams (you may skip exercise 13 of the first exam)

Ignore the comments on derivatives in the solutions since we have not covered thatTuesday 17/5 Consultation and exercise class Lecture Thursday 19/5 Slides Cancelled! Turing machines, Push-down automata, summary of the course

Sections 8