## See link at Time Edit for the up-to-date schedule during VT16.

Lectures Mondays13:15--15:00 in HB3

Tuesday 22/39:00--11:45 in HA4,ONLYin week 1

Thursdays13:15--15:00 in HB3,EXCEPTweeks 4 and 5

Wednesday 27/413:15--15:00 in HB3,ONLYin week 4Exercise sessions Thursday 24/310:00--11:45 in HC3,ONLYweek 1

ForALLstudents who need to recap on discrete math concepts

Mondays15:15--17:00 in EA, weeks 2--8

Tuesdays10:00--11:45 in EA, weeks 2--8Consultation time Wednesdays15:15--17:00 in EL41, weeks 2--8

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

Lectures Monday 21/3

13:15--15:00, HB3Ana Bove Slides-1 Overview and organisation of the course. Tuesday 22/3

9:00--11:45, HA4Ana Bove Slides-2 Recap on logic, sets, functions and relations;

Central concepts in automata theory;

Section 1.5 and more.Thursday 24/3

13:15--15:00, HB3Ana Bove Slides-3 Formal proofs, inductively defined sets, proofs by (structural) induction;

Sections 1.2--1.4 in the book.Exercise Thursday 24/3

10:00--11:45, HC3Ana Bove Recap

ExercisesLogic, sets, relations and functions. Assignment See Week 2

[top]

Lectures Monday 11/4

13:15--15:00, HB3Ana Bove Slides-4 DFA;

Sections 2--2.2.Thursday 14/4

13:15--15:00, HB3Ana Bove Slides-5 NFA, subset construction algorithm, equivalence between DFA and NFA;

Sections 2.3--2.3.5, brief on 2.4.Exercises Monday 11/4

15:15--17:00, EAAndrea Exercise-1 Formal proofs, alphabets and words. Tuesday 12/4

10:00--11:45, EAVictor Consultation Wednesday 13/4

15:15--17:00, EL41Ana Bove Assignment Deadline: Thursday 14/4 23:59Assignment-1 Formal proofs, alphabets and words.

[top]

Lectures Monday 18/4

13:15--15:00, HB3Ana Bove Slides-6 More on NFA, NFA with epsilon transitions;

Sections 2.3.6, 2.5--2.5.5.Thursday 21/4

13:15--15:00, HB3Ana Bove Slides-7 Regular expressions, algebraic laws for RE, from FA to RE;

Sections 3.1, 3.4, 3.2.2.Exercises Monday 18/4

15:15--17:00, EADaniel Exercise-2 DFA, NFA, NFA with epsilon transitions;

Some exercises should be done in week 4.Tuesday 19/4

10:00--11:45, EAMarco Consultation Wednesday 20/4

15:15--17:00, EL41Ana Bove Assignment Deadline:~~Thursday 21/4~~Sunday 24th 23:59Assignment-2 DFA and NFA.

[top]

Lectures Monday 25/4

13:15--15:00, HB3Ana Bove Slides-8 From RE to FA, Pumping Lemma for RL, closure properties of RL;

Sections 3.2.3, 4--4.2.Wednesday 27/4

13:15--15:00, HB3Ana Bove Slides-9 Decision properties of RL, equivalence of RL, minimisation of automata;

Sections 4.3--4.4.Exercises Monday 25/4

15:15--17:00, EADaniel Exercise-3 Regular expressions. Tuesday 26/4

10:00--11:45, EAMarco Consultation Wednesday 27/4

15:15--17:00, EL41Ana Bove Assignment Deadline:~~Thursday 28/4~~Friday 29/4 23:59Assignment-3 Epsilon-NFA, RE.

[top]

Lectures Monday 2/5

13:15--15:00, HB3Ana Bove Slides-10 Context-free grammars, derivations, parse trees, proofs in grammars;

Sections 5--5.2.2.Exercises Monday 2/5

15:15--17:00, EAAndrea Exercise-4 Properties of RL, minimisation of automata. Tuesday 3/5

10:00--11:45, EAVictor Consultation Wednesday 4/5

15:15--17:00, EL41Ana Bove Assignment Deadline: Monday 9/5 23:59Assignment-4 Regular languages.

[top]

Lecture Monday 9/5

13:15--15:00, HB3Ana Bove Slides-11 Inference, derivations and parse trees, ambiguous grammars, regular grammars;

Sections 5.2.3--5.2.6, 5.4.Thursday 12/5

13:15--15:00, HB3Ana Bove Slides-12 Chomsky hierarchy, simplifications, normal forms and Pumping lemma for CFL;

Sections 7--7.2.Exercises Monday 9/5

15:15--17:00, EADaniel Exercise-5 Context-free grammars. Tuesday 10/5

10:00--11:45, EAMarco Consultation Wednesday 11/5

15:15--17:00, EL41Ana Bove Assignment Deadline: Monday 16/5 23:59Assignment-5 Context-free grammars.

[top]

Lectures Monday 16/5

13:15--15:00, HB3Ana Bove Slides-13 Closure properties of CFL, decision properties of CFL.

Guest lecture by Andreas Abel onProgramming Language Technology: Putting Formal Languages to Work

Sections 7.3-7.4.Thursday 19/5

13:15--15:00, HB3Ana Bove Slides-14 Push-down automata (just the idea). Turing machines.

Sections 6 (just the idea) and 8.Exercises Monday 16/5

15:15--17:00, EAVictor Exercise-6 Context-free languages. Tuesday 17/5

10:00--11:45, EAVictor Consultation Wednesday 18/5

15:15--17:00, EL41Ana Bove Assignment Deadline: Monday 23/5 23:59Assignment-6 Context-free languages.

[top]

Lecture Monday 23/5

13:15--15:00, HB3Ana Bove Slides-15 Turing machines. Summary of the course. Lecture/

ExerciseThursday 26/5

13:15--15:00, HB3Ana Bove Exam 130528 (with solution),

Exam 130821 (with solution)Old exams Exercises Monday 23/5

15:15--17:00, EAAndrea Exercise-7 Turing Machines. Tuesday 24/5

10:00--11:45, EAMarco Consultation Wednesday 25/5

15:15--17:00, EL41Ana Bove Assignment Deadline: Friday 27/5 23:59Assignment-7 Turing Machines.

[top]