Plan for the Lectures, Exercise Sessions and Assignments

Finite Automata Theory and Formal Languages

TMV027/DIT321, LP4 2013

[Main page]

Lectures Monday 18/3 13:15--15:00 in EC, ONLY study week 1
Tuesdays mornings in 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:00 in EC, all study week but 6
Exercise session Mondays 13:15--15:00 in 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:00
Consultation time Thursdays 10:00--11:45, all weeks but study week 6; week 1 in EL42, other weeks in group room 5217

See link at Time Edit for further details.


Schedule per Week

[
Week 1 | Week 2 | Week 3 | Week 4 | Week 5 | Week 6 | Week 7 | Week 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.

Week 1

Lectures Monday 18/3
13:15--15:00, EC
Slides-1 Organisation and overview of the course.
  Tuesday 19/3
9:00-11:45, EC
Slides-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, EC
Slides-3 Formal proofs, inductively defined sets, proofs by (structural) induction;
Sections 1.2--1.4 in the book.
Consultation/
Exercise
Thursday 21/3
10:00-12:00, EL42
Recap
Exercises
Logic, sets, relations and functions.
Assignment Deadline: Thursday 11/4 23:59 Assignment-1 Formal proofs (10 pts).

[top]

Easter Break

Week 2

Exercise Monday 8/4
13:15--15:00, EC
Exercise-1 Formal proofs, alphabets and words.
Lectures Tuesday 9/4
9:00-11:45, EC
Slides-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, EC
Slides-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, 5217
Assignment Deadline: Thursday 18/4 23:59 Assignment-2 DFA and NFA (10 pts).

[top]

Week 3

Exercise Monday 15/4
13:15--15:00, EC
Exercise-2 DFA, NFA, NFA with epsilon transitions;
Some exercises should be done in week 4.
Lectures Tuesday 16/4
10:00-11:45, EC
Slides-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, EC
Slides-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, 5217
Assignment Deadline: Thursday 25/4 23:59 Assignment-3 Epsilon-NFA, RE (9.5 pts).

[top]

Week 4

Exercise Monday 22/4
13:15--15:00, EC
Exercise-3 Regular expressions.
Lectures Tuesday 23/4
9:00-11:45, EC
Slides-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, EC
Slides-9 Decision properties of RL, equivalence of RL, minimisation of automata;
Sections 4.3--4.4.
Consultation Thursday 25/4
10:00-12:00, 5217
Assignment Deadline: Friday 3/5 23:59 Assignment-4 Regular languages (10.5 pts).

[top]

Week 5

Exercise Monday 29/4
13:15--15:00, EC
Exercise-4 Properties of RL, minimisation of automata.
Lectures Tuesday 30/4
9:00-11:45, EC
Slides-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, EC
Slides-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, 5217
Assignment Deadline: Monday 13/5 23:59 Assignment-5 Context free grammars (10 pts).

[top]

Week 6

Exercise Monday 6/5
13:15--15:00, EC
Exercise-5 Context free grammars.
Lecture Tuesday 7/5
10:00-11:45, EC
Slides-12 Chomsky hierarchy, simplifications, normal forms and Pumping lemma for CFL;
Section 7--7.2.
Assignment See week 7

[top]

Week 7

Exercise Monday 13/5
13:15--15:00, EC
Exercise-6 Context free languages;
Some exercises should be done in week 8.
Lecture Tuesday 14/5
9:00-11:45, EC
Slides-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/
Exercise
Thursday 16/5
13:15--15:00, EC
Exam 100527 (with solution),
Exam 100827 (with solution)
Old exams
Consultation Thursday 16/5
10:00-12:00, 5217
Assignment Deadline: Monday 20/5 23:59 Assignment-6 Context free languages (10 pts).

[top]

Week 8

Exercise Monday 20/5
13:15--15:00, EC
See week 7 Context free languages.
Lecture Tuesday 21/5
10:00-11:45, EC
Notes on TM Lecture by Laura Kovács: Turing machines;
Section 8.
Lecture/
Exercise
Thursday 23/5
13:15--15:00, EC
Notes on TM (2);
Overview slides;
Exercise-7
Turing machines; summary of the course.
Consultation Thursday 23/5
10:00-12:00, 5217
Assignment Deadline: Sunday 26/5 23:59 Assignment-7 Turing Machines (4 pts).

[top]