Weekly Plan for the Lectures, Exercise Sessions and Assignments

Finite Automata Theory and Formal Languages

TMV027/DIT321, LP4 2015


[Main page]

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

Lectures Mondays 13:15--15:00, in HB3 (weeks 1), HC3 (week 4) and HC2 (weeks 2--3 and 5--8)

Tuesday 24/3 9:00--11:45, in HB3 ONLY in week 1

Thursdays 13:15--15:00 in HB3 (weeks 1--3 & 5) and HC2 (weeks 7 & 8)
Thursday 10:00--11:45 in HC2 ONLY in week 4
Exercise sessions Thursday 26/3 10:00--11:45 for ALL students who need to recap on discrete math concepts, in HC3 (week 1)

Mondays 15:15--17:00 in EE (weeks 2--5 & 8)
Tuesday 15:15--17:00 in EF (week 6)
Monday 10:00--11:45 in EE (week7)

Tuesdays 10:00--11:45, in EF (weeks 2--8). Mainly for students NOT in their first year.
Tuesdays 10:00--11:45, in EE (weeks 2--3, 5--8)
Tuesday 15:15--17:00 in EF (week 4)
Consultation time Wednesdays 15:15--17:00 in EL41 (week2) and ES53 (weeks 3--6 & 8)
Thursday 10:00--11:45 in EE (week 7)


Plan per Week during VT15

[
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 23/3
13:15--15:00, HB3
Ana Bove Slides-1 Organisation and overview of the course.
  Tuesday 24/3
9:00--11:45, HB3
Ana Bove Slides-2 Recap on logic, sets, functions and relations;
Central concepts in automata theory;
Section 1.5 and more.
  Thursday 26/3
13:15--15:00, HB3
Ana Bove Slides-3 Formal proofs, inductively defined sets, proofs by (structural) induction;
Sections 1.2--1.4 in the book.
Exercise Thursday 26/3
10:00--11:45, HC3
Simon Huber Recap
Exercises
Logic, sets, relations and functions.
Assignment See Week 2

[top]

Week 2

Lectures Monday 30/3
13:15--15:00, HC2
Ana Bove Slides-4 DFA;
Sections 2--2.2.
  Thursday 2/4
13:15--15:00, HB3
Ana Bove Slides-5 NFA, subset construction algorithm, equivalence between DFA and NFA;
Sections 2.3--2.3.5, brief on 2.4.
Exercises Monday 30/3
15:15--17:00, EE
Andrea Vezzosi Exercise-1 Formal proofs, alphabets and words.
  Tuesday 31/3
10:00--11:45, EF
Simon Huber
Consultation Wednesday 1/4
15:15--17:00, EL41
Ana Bove
Assignment Deadline: Thursday 2/4 23:59 Assignment-1 Formal proofs.

[top]

Easter Break

Week 3

Lectures Monday 20/4
13:15--15:00, HC2
Ana Bove Slides-6 More on NFA, NFA with epsilon transitions;
Sections 2.3.6, 2.5--2.5.5.
  Thursday 23/4
13:15--15:00, HB3
Ana Bove Slides-7 Regular expressions, algebraic laws for RE, from FA to RE;
Sections 3.1, 3.4, 3.2.2.
Exercises Monday 20/4
15:15--17:00, EE
Daniel Schoepe Exercise-2 DFA, NFA, NFA with epsilon transitions;
Some exercises should be done in week 4.
  Tuesday 21/4
10:00--11:45, EF
Pablo Buiras
Consultation Wednesday 22/4
15:15--17:00, ES53
Ana Bove
Assignment Deadline: Monday 27/4 23:59 Assignment-2 DFA and NFA.

[top]

Week 4

Lectures Monday 27/4
13:15--15:00, HC3
Ana Bove Slides-8 From RE to FA, Pumping Lemma for RL, closure properties of RL;
Sections 3.2.3, 4--4.2.
  Thursday 30/4
10:00--11:45, HC2
Ana Bove Slides-9 Decision properties of RL, equivalence of RL, minimisation of automata;
Sections 4.3--4.4.
Exercises Monday 27/4
15:15--17:00, EE
Andrea Vezzosi Exercise-3 Regular expressions.
  Tuesday 28/4
15:15--17:00, EF
Simon Huber
Consultation Wednesday 29/4
15:15--17:00, ES53
Ana Bove
Assignment Deadline: Monday 4/5 23:59 Assignment-3 Epsilon-NFA, RE.

[top]

Week 5

Lectures Monday 4/5
13:15--15:00, HC2
Ana Bove Slides-10 Context free grammars, derivations, parse trees, proofs in grammars;
Sections 5--5.2.2.
  Thursday 7/5
13:15--15:00, HB3
Ana Bove Slides-11 Inference, derivations and parse trees, ambiguous grammars, regular grammars;
Sections 5.2.3--5.2.6, 5.4.
Exercises Monday 4/5
15:15--17:00, EE
Andrea Vezzosi Exercise-4 Properties of RL, minimisation of automata.
  Tuesday 5/5
10:00--11:45, EF
Pablo Buiras
Consultation Wednesday 6/5
13:15--15:00, ES53
Ana Bove
Assignment Deadline: Monday 11/5 23:59 Assignment-4 Regular languages.

[top]

Week 6

Lecture Monday 11/5
13:15--15:00, HC2
Ana Bove Slides-12 Chomsky hierarchy, simplifications, normal forms and Pumping lemma for CFL;
Sections 7--7.2.
Exercises Tuesday 12/5
10:00--11:45, EF
Simon Huber Exercise-5 Context free grammars.
  Tuesday 12/5
15:15--17:00, EF
Daniel Schoepe
Consultation Wednesday 13/5
15:15--17:00, ES53
Ana Bove
Assignment Deadline: Monday 18/5 23:59 Assignment-5 Context free grammars.

[top]

Week 7

Lectures Monday 18/5
13:15--15:00, HC2
Ana Bove Slides-13 Closure properties of CFL, decision properties of CFL, push-down automata (just the idea).
Sections 7.3-7.4, 6 (just the idea).
  Thursday 21/5
13:15--15:00, HC2
Ana Bove Slides-14 Turing machines.
Section 8.
Guest lecture by Aarne Ranta on Automata and grammars in Programming language technology
Exercises Monday 18/5
10:00--11:45, EE
Daniel Schoepe Exercise-6 Context free languages.
  Tuesday 19/5
10:00--11:45, EF
Pablo Buiras
Consultation Thursday 21/5
10:00--11:45, EE
Ana Bove
Assignment Deadline: Monday 25/5 23:59 Assignment-6 Context free languages.

[top]

Week 8

Lecture Monday 25/5
13:15--15:00, HC2
Ana Bove Slides-15 Turing machines, summary of the course.
Lecture/
Exercise
Thursday 28/5
13:15--15:00, HC2
Ana Bove Exam 130528 (with solution),
Exam 130821 (with solution)
Old exams
Exercises Monday 25/5
15:15--17:00, EE
Simon Huber Exercise-7 Turing Machines.
  Tuesday 26/5
10:00--11:45, EF
Andrea Vezzosi
Consultation Wednesday 21/5
15:15--17:00, ES53
Ana Bove
Assignment Deadline: Friday 29/5 23:59 Assignment-7 Turing Machines.

[top]