Lectures Mondays 13:15--15:00 and Tuesdays 10:00--11:45, all weeks but week 6

Thursdays 10:00--11:45, only weeks 1 and 6

See below for information about the rooms.Exercise session Thursdays 13:15--15:00, in EF all weeks but weeks 2 and 8

On week 2 the room is HC3.

On week 8 there is no exercise class.Consultation time Thursdays 10:00--11:45 in group room 5205, all weeks but weeks 1 and 6 See link at Time Edit for details.

**Note:** Below is a tentative schedule for lectures and excersise
session. The content of each lecture and excersise session will be
updated during the running of the course to take into account possible
deviations.

Lectures Monday 12/3 HC4 Slides-1 Organisation and overview of the course Tuesday 13/3 HA2 Slides-2 Formal proofs, inductively defined sets, proofs by (structural) induction

Sections 1.2--1.4 in the bookThursday 15/3 EA Slides-3 Central concepts in discrete mathematics and automata theory

Section 1.5Exercise Thursday 15/3 EF Ex-1 Formal proofs, alphabets and words Assignment Deadline: Thursday 22/3Ass-1 Formal proofs

[top]

Lectures Monday 19/3 HC3 Slides-4 DFA

Sections 2--2.2Tuesday 20/3 EC Slides-5 NFA, subset construction algorithm, equivalence between DFA and NFA

Sections 2.3--2.3.5Consultation Thursday 22/3 5205 Exercise Thursday 22/3 HC3 Ex-2 DFA, NFA, NFA with epsilon transitions

Some exercises should be done in week 3.Assignment Deadline: Thursday 29/3Ass-2 DFA and NFA

[top]

Lectures Monday 26/3 EB Slides-6 NFA, NFA with epsilon transitions

Sections 2.3.6--2.5.5Tuesday 27/3 EC Slides-7 Regular expressions, from FA to RE

Sections 3--3.1, 3.4, 3.2.2Consultation Thursday 29/3 5205 Exercise Thursday 29/3 EF Ex-3 Regular expressions

Some exercises should be done in week 4.Assignment Deadline: Thursday 19/4Ass-3 Epsilon-NFA, RE

[top]

Lectures Monday 16/4 EB Slides-8 From RE to FA, pumping Lemma for RL, closure properties of regular languages

Sections 3.2.3, 4--4.2.1Tuesday 17/4 EC Slides-9 Closure and decision properties of regular languages.

Sections 4.2.2--4.3Consultation Thursday 19/4 5205 Exercise Thursday 19/4 EF Ex-4 Properties of RL, minimisation of automata

Some exercises should be done in week 5.Assignment Deadline: Thursday 26/4Ass-4 Regular languages

[top]

Lectures Monday 23/4 EB Slides-10 Equivalence of RL, minimisation of automata

Section 4.4Tuesday 24/4 EC Slides-11 Context free grammars, derivations, parse trees

Sections 5--5.2Consultation Thursday 26/4 5205 Exercise Thursday 26/4 EF Ex-5 Context free grammars

Some exercises should be done in week 6.Assignment Deadline: Monday 7/5Ass-5 Context free grammars

[top]

Lecture Thursday 3/5 EA Slides-12 Ambiguous grammars, Chomsky hierarchy

Section 5.4Exercise Thursday 3/5 EF Same as week 5 Context free grammars

[top]

Lecture Monday 7/5 EB Slides-13 Normal forms and Pumping lemma for CFL

Section 7--7.2Tuesday 8/5 EC Slides-14 Closure and decision properties of CFL

Sections 7.3--7.4Consultation Thursday 10/5 5205 Exercise Thursday 10/5 EF Ex-6 Context free grammars and languages Assignment Deadline: Monday 14/5Ass-6 Context free languages

[top]

Lecture Monday 14/5 EB Slides-15 Turing machines, Push-down automata, summary of the course

Section 8Exercise Tuesday 15/5 EC Exam 100527, Exam 100827

Older exams (you may skip exercise 13 of the first exam) and some solutions (ignore the comments on derivatives in the solutions since we have not covered that)

[top]