Weekly Plan for the Lectures, Exercise Sessions and Assignments

Finite Automata Theory and Formal Languages

TMV027/DIT321, LP4 2014


[Main page]

Lectures Mondays 13:15--15:00, in HB3 (weeks 1--7) and HC4 (week 8)
Tuesday 18/3 9:00--11:45, in HA1 ONLY in week 1
Thursdays 13:15--15:00 all study week but week 5, in HB3
Exercise sessions Thursday 20/3 10:00--11:45 for ALL students who need to recap on discrete math concepts, in HC3 (week 1)
Tuesdays 10:00--11:45, in EF (weeks 2--8). Mainly for students NOT in their first year.
Thursdays 10:00--11:45, in EE (weeks 2--3, 6--8) and EB (week 4). Mainly for FIRST years students
Wednesday 30/4 10:00--11:45, in EF (ONLY in week 5). Mainly for FIRST years students
Consultation time Wednesdays 15:15--17:00 all weeks but study week 1 and week 5, in ES51

See link at Time Edit for further details.


Plan 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 17/3
13:15--15:00, HB3
Ana Bove Slides-1 Organisation and overview of the course.
  Tuesday 18/3
9:00--11:45, HA1
Ana Bove Slides-2 Recap on logic, sets, functions and relations;
Central concepts in automata theory;
Section 1.5 and more.
  Thursday 20/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 20/3
10:00--11:45, HC3
Simon Huber Recap
Exercises
Logic, sets, relations and functions.
Assignment Deadline: Sunday 30/3 23:59 Assignment-1 Formal proofs.

[top]

Week 2

Lectures Monday 24/3
13:15--15:00, HB3
Ana Bove Slides-4 DFA;
Sections 2--2.2.
  Thursday 27/3
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 Tuesday 25/3
10:00--11:45, EF
Simon Huber Exercise-1 Formal proofs, alphabets and words.
  Thursday 27/3
10:00--11:45, EE
Simon Huber
Consultation Wednesday 26/3
15:15--17:00, ES51
Ana Bove
Assignment Deadline: Sunday 6/4 23:59 Assignment-2 DFA and NFA.

[top]

Week 3

Lectures Monday 31/3
13:15--15:00, HB3
Ana Bove Slides-6 More on NFA, NFA with epsilon transitions, regular expressions;
Sections 2.3.6, 2.5--2.5.5, 3.1.
  Thursday 3/4
13:15--15:00, HB3
Ana Bove Slides-7 More on RE, algebraic laws for RE, from FA to RE;
Sections 3.4, 3.2.2.
Exercises Tuesday 1/4
10:00--11:45, EF
Simon Huber Exercise-2 DFA, NFA, NFA with epsilon transitions;
Some exercises should be done in week 4.
  Thursday 3/4
10:00--11:45, EE
Simon Huber
Consultation Wednesday 2/4
15:15--17:00, ES51
Ana Bove
Assignment Deadline: Sunday 13/4 23:59 Assignment-3 Epsilon-NFA, RE.

[top]

Week 4

Lectures Monday 7/4
13:15--15:00, HB3
Ana Bove Slides-8 From RE to FA, Pumping Lemma for RL, closure properties of RL;
Sections 3.2.3, 4--4.2.
  Thursday 10/4
13:15--15:00, HB3
Ana Bove Slides-9 Decision properties of RL, equivalence of RL, minimisation of automata;
Sections 4.3--4.4.
Exercises Tuesday 8/4
10:00--11:45, EF
Inari Listenmaa Exercise-3 Regular expressions.
  Thursday 10/4
10:00--11:45, EB
Simon Huber
Consultation Wednesday 9/4
15:15--17:00, ES51
Ana Bove
Assignment Deadline: Sunday 4/5 Monday 5/5 23:59 Assignment-4 Regular languages.

[top]

Easter Break

Week 5

Lectures Monday 28/4
13:15--15:00, HB3
Ana Bove Slides-10 Context free grammars, derivations, parse trees, proofs in grammars;
Section 5--5.2.2.
Exercise Tuesday 29/4
10:00--11:45, EF
Andrea Vezzosi Exercise-4 Properties of RL, minimisation of automata.
  Wednesday 30/4
10:00--11:45, EF
Pablo Buiras
  Friday 2/5
15:15--17:00, EF
Ana Bove NEW!
Consultation Wednesday 30/4
13:15--15:00, ES51
Ana Bove NEW!

[top]

Week 6

Lecture Monday 5/5
13:15--15:00, HB3
Ana Bove Slides-11 Inference, derivations and parse trees, ambiguous grammars, regular grammars;
Section 5.2.3--5.2.6, 5.4.
  Thursday 8/5
13:15--15:00, HB3
Ana Bove Slides-12 Chomsky hierarchy, simplifications, normal forms and Pumping lemma for CFL;
Section 7--7.2.
Exercise Tuesday 6/5
10:00--11:45, EF
Daniel Hausknecht
Pablo Buiras
Exercise-5 Context free grammars.
  Thursday 8/5
10:00--11:45, EE
Pablo Buiras
Consultation Wednesday 7/5
15:15--17:00, ES51
Ana Bove
Assignment Deadline: Monday 12/5 23:59 Assignment-5 Context free grammars.

[top]

Week 7

Lecture Monday 12/5
13:15--15:00, HB3
Ana Bove Slides-13 Decision properties of CFL;
Section 7.4.
Guest lecture by Prof. Aarne Ranta on Automata and grammars in Programming language technology
  Thursday 15/5
13:15--15:00, HB3
Ana Bove Slides-14 Closure properties of CFL, push-down automata (just the idea), Turing machines;
Sections 7.3, 6 (just the idea) and 8.
Exercise Tuesday 13/5
10:00--11:45, EF
Inari Listenmaa Exercise-6 Context free languages.
  Thursday 15/5
10:00--11:45, EE
Pablo Buiras
Consultation Wednesday 14/5
15:15--17:00, ES51
Ana Bove
Assignment Deadline: Monday 19/5 23:59 Assignment-6 Context free languages.

[top]

Week 8

Lecture Monday 19/5
13:15--15:00, HC4
Ana Bove Slides-15 Turing machines, summary of the course.
Lecture/
Exercise
Thursday 22/5
13:15--15:00, HB3
Ana Bove Exam 130528,
Exam 130821
Old exams
Exercise Tuesday 20/5
10:00--11:45, EF
Andrea Vezzosi Exercise-7 Turing Machines.
  Thursday 22/5
10:00--11:45, EE
Pablo Buiras
Consultation Wednesday 21/5
15:15--17:00, ES51
Ana Bove
Assignment Deadline: Sunday 25/5 23:59 Assignment-7 Turing Machines.

[top]