Lectures Monday 18/313:15--15:00 in EC,ONLYstudy week 1

Tuesdays morningsin EC

Note:Check the schedule per week to see if the lecture starts at 9:00 or at 10:00 during that week

Thursdays 13:15--15:00in EC, all study week but 6Exercise session Mondays 13:15--15:00in EC, all weeks but study week 1

Note:If there is need and the room is not booked for something else, exercise sessions can be extended until 16:00Consultation time Thursdays 10:00--11:45, all weeks but study week 6; week 1 in EL42, other weeks in group room 5217See link at Time Edit for further details.

**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 18/3

13:15--15:00, ECSlides-1 Organisation and overview of the course. Tuesday 19/3

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

Central concepts in automata theory;

Section 1.5 and more.Thursday 21/3

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

Sections 1.2--1.4 in the book.Consultation/

ExerciseThursday 21/3

10:00-12:00, EL42Recap

ExercisesLogic, sets, relations and functions. Assignment Deadline: Thursday 11/4 23:59Assignment-1 Formal proofs (10 pts).

[top]

Exercise Monday 8/4

13:15--15:00, ECExercise-1 Formal proofs, alphabets and words. Lectures Tuesday 9/4

9:00-11:45, ECSlides-4 Guest Lecture by Anders Mörtberg: Inductive proofs in proof assistants (abstract, slides, Agda code);

DFA;

Sections 2--2.2.Thursday 11/4

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

Sections 2.3--2.3.5, brief on 2.4.Consultation Thursday 11/4

10:00-12:00, 5217Assignment Deadline: Thursday 18/4 23:59Assignment-2 DFA and NFA (10 pts).

[top]

Exercise Monday 15/4

13:15--15:00, ECExercise-2 DFA, NFA, NFA with epsilon transitions;

Some exercises should be done in week 4.Lectures Tuesday 16/4

10:00-11:45, ECSlides-6 More on NFA, NFA with epsilon transitions, regular expressions;

Sections 2.3.6, 2.5--2.5.5, 3.1.Thursday 18/4

13:15--15:00, ECSlides-7 More on RE, algebraic laws for RE, from FA to RE;

Sections 3.4, 3.2.2.Consultation Thursday 18/4

10:00-12:00, 5217Assignment Deadline: Thursday 25/4 23:59Assignment-3 Epsilon-NFA, RE (9.5 pts).

[top]

Exercise Monday 22/4

13:15--15:00, ECExercise-3 Regular expressions. Lectures Tuesday 23/4

9:00-11:45, ECSlides-8 Guest Lecture by Wolfgang Ahrendt: Büchi automata and their application to software verification (abstract, slides);

From RE to FA, Pumping Lemma for RL, closure properties of RL;

Sections 3.2.3, 4--4.2.Thursday 25/4

13:15--15:00, ECSlides-9 Decision properties of RL, equivalence of RL, minimisation of automata;

Sections 4.3--4.4.Consultation Thursday 25/4

10:00-12:00, 5217Assignment Deadline: Friday 3/5 23:59Assignment-4 Regular languages (10.5 pts).

[top]

Exercise Monday 29/4

13:15--15:00, ECExercise-4 Properties of RL, minimisation of automata. Lectures Tuesday 30/4

9:00-11:45, ECSlides-10 Context free grammars, derivations, parse trees, proofs in grammars;

Section 5--5.2.2.Guest Lecture by Martin Fabian: Supervisory Control Theory -- A Practical Application of Automata Theory (abstract, slides).Thursday 2/5

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

Section 5.2.3--5.2.6, 5.4.Consultation Thursday 2/5

10:00-12:00, 5217Assignment Deadline: Monday 13/5 23:59Assignment-5 Context free grammars (10 pts).

[top]

Exercise Monday 6/5

13:15--15:00, ECExercise-5 Context free grammars. Lecture Tuesday 7/5

10:00-11:45, ECSlides-12 Chomsky hierarchy, simplifications, normal forms and Pumping lemma for CFL;

Section 7--7.2.Assignment See week 7

[top]

Exercise Monday 13/5

13:15--15:00, ECExercise-6 Context free languages;

Some exercises should be done in week 8.Lecture Tuesday 14/5

9:00-11:45, ECSlides-13 Closure and decision properties of CFL, undecidable problems, push-down automata;

Sections 7.3--7.4.Guest Lecture by Aarne Ranta: Using grammars in compilers and translation (abstract).Lecture/

ExerciseThursday 16/5

13:15--15:00, ECExam 100527 (with solution),

Exam 100827 (with solution)Old exams Consultation Thursday 16/5

10:00-12:00, 5217Assignment Deadline: Monday 20/5 23:59Assignment-6 Context free languages (10 pts).

[top]

Exercise Monday 20/5

13:15--15:00, ECSee week 7 Context free languages. Lecture Tuesday 21/5

10:00-11:45, ECNotes on TM Lecture by Laura Kovács: Turing machines;

Section 8.Lecture/

ExerciseThursday 23/5

13:15--15:00, ECNotes on TM (2);

Overview slides;

Exercise-7Turing machines; summary of the course. Consultation Thursday 23/5

10:00-12:00, 5217Assignment Deadline: Sunday 26/5 23:59Assignment-7 Turing Machines (4 pts).

[top]