Plan for the Lectures, Exercise Sessions and Assignments

[Main page]

Lectures: Mondays 13:15--15:00 in HA2 and Tuesdays 10:00--11:45 in HC3.
Extra lecture only the first week: Thursday 10:00-11:45 in HA3.
Exercise sessions: Thursdays 13:15--15:00 in EB.

See link at Time Edit for details.

Week 1

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 book
	Thursday 23/3	Slides	Central concepts of automata theory, DFA Sections 1.5, 2--2.2
Exercises	Thursday 24/3	Text	Formal proofs, alphabets and words
Assignment	Deadline: Thursday 31/3	Text	Formal proofs

Lectures	Monday 28/3	Slides	DFA, NFA, subset construction algorithm Sections 2.3--2.3.5
	Tuesday 29/3	Slides	Equivalence between DFA and NFA, NFA with epsilon transitions Sections 2.3.5--2.5.3
Exercises	Thursday 31/3	Text	DFA. NFA, NFA with epsilon transitions Some exercises should be done in week 3.
Assignment	Deadline: Thursday 7/4	Text	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.4
	Tuesday 5/4	Slides	Equivalence between AF and RE, Pumping Lemma for RL Sections 3.2.2--3.2.3, 4--4.1
Exercises	Thursday 7/4	Text	Regular expressions Some exercises should be done in week 4.
Assignment	Deadline: Thursday 14/4	Text	Epsilon-NFA, RE

Lectures	Monday 11/4	Slides	Closure and decision properties of regular languages Sections 4.2--4.3
	Tuesday 12/4	Slides	Equivalence of RL, minimisation of automata Section 4.4
Exercises	Thursday 14/4	Text	Properties of RL, minimisation of automata
Assignment	Deadline: Thursday 5/5	Text	Regular languages

Lectures	Monday 2/5	Slides	Context free grammars, derivations, parse trees Sections 5--5.2
	Tuesday 3/5	Slides	Ambiguous grammars, Chomsky hierarchy Section 5.4
	Thursday 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/5	Text	Context free grammars

Lectures	Monday 9/5	Slides	Normal forms and Pumping lemma for CFG Section 7--7.2
	Tuesday 10/5	Slides	Properties of CFG Sections 7.3--7.4
Exercises	Thursday 12/5	Text	Context free languages
Assignment	Deadline: Thursday 19/5	Text	Context free languages

Exercises	Monday 16/5	Exams Solutions	Solving old exams (you may skip exercise 13 of the first exam) Ignore the comments on derivatives in the solutions since we have not covered that
	Tuesday 17/5		Consultation and exercise class
Lecture	Thursday 19/5	Slides	Cancelled! Turing machines, Push-down automata, summary of the course Sections 8