Weekly Plan for the Lectures, Exercise Sessions and Assignments

Finite Automata Theory and Formal Languages

TMV027/DIT321, LP4 2016

[Main page]

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

Lectures Mondays 13:15--15:00 in HB3

Tuesday 22/3 9:00--11:45 in HA4, ONLY in week 1

Thursdays 13:15--15:00 in HB3, EXCEPT weeks 4 and 5
Wednesday 27/4 13:15--15:00 in HB3, ONLY in week 4
Exercise sessions Thursday 24/3 10:00--11:45 in HC3, ONLY week 1
For ALL students who need to recap on discrete math concepts

Mondays 15:15--17:00 in EA, weeks 2--8
Tuesdays 10:00--11:45 in EA, weeks 2--8
Consultation time Wednesdays 15:15--17:00 in EL41, weeks 2--8


Plan per Week during VT16

 [ 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 21/3
13:15--15:00, HB3 		Ana Bove Slides-1 Overview and organisation of the course.
  Tuesday 22/3
9:00--11:45, HA4		 Ana 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, HB3		 Ana 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, HC3		 Ana Bove Recap
Exercises		 Logic, sets, relations and functions.
Assignment See Week 2

[top]

Easter Break

Week 2
Lectures Monday 11/4
13:15--15:00, HB3 		Ana Bove Slides-4 DFA;
Sections 2--2.2.
  Thursday 14/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 11/4
15:15--17:00, EA		 Andrea Exercise-1 Formal proofs, alphabets and words.
  Tuesday 12/4
10:00--11:45, EA		 Victor
Consultation Wednesday 13/4
15:15--17:00, EL41		 Ana Bove
Assignment Deadline: Thursday 14/4 23:59 Assignment-1 Formal proofs, alphabets and words.

[top]

Week 3

Lectures Monday 18/4
13:15--15:00, HB3 		Ana 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, 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 18/4
15:15--17:00, EA		 Daniel Exercise-2 DFA, NFA, NFA with epsilon transitions;
Some exercises should be done in week 4.
  Tuesday 19/4
10:00--11:45, EA		 Marco
Consultation Wednesday 20/4
15:15--17:00, EL41		 Ana Bove
Assignment Deadline: Thursday 21/4 Sunday 24th 23:59 Assignment-2 DFA and NFA.

[top]

Week 4

Lectures Monday 25/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.
  Wednesday 27/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 Monday 25/4
15:15--17:00, EA		 Daniel Exercise-3 Regular expressions.
  Tuesday 26/4
10:00--11:45, EA		 Marco
Consultation Wednesday 27/4
15:15--17:00, EL41		 Ana Bove
Assignment Deadline: Thursday 28/4 Friday 29/4 23:59 Assignment-3 Epsilon-NFA, RE.

[top]

Week 5

Lectures Monday 2/5
13:15--15:00, HB3 		Ana 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, EA		 Andrea Exercise-4 Properties of RL, minimisation of automata.
  Tuesday 3/5
10:00--11:45, EA		 Victor
Consultation Wednesday 4/5
15:15--17:00, EL41		 Ana Bove
Assignment Deadline: Monday 9/5 23:59 Assignment-4 Regular languages.

[top]

Week 6

Lecture Monday 9/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.
  Thursday 12/5
13:15--15:00, HB3 		Ana 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, EA		 Daniel Exercise-5 Context-free grammars.
  Tuesday 10/5
10:00--11:45, EA		 Marco
Consultation Wednesday 11/5
15:15--17:00, EL41		 Ana Bove
Assignment Deadline: Monday 16/5 23:59 Assignment-5 Context-free grammars.

[top]

Week 7

Lectures Monday 16/5
13:15--15:00, HB3 		Ana Bove Slides-13 Closure properties of CFL, decision properties of CFL.
Guest lecture by Andreas Abel on Programming Language Technology: Putting Formal Languages to Work
Sections 7.3-7.4.
  Thursday 19/5
13:15--15:00, HB3		 Ana 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, EA		 Victor Exercise-6 Context-free languages.
  Tuesday 17/5
10:00--11:45, EA		 Victor
Consultation Wednesday 18/5
15:15--17:00, EL41		 Ana Bove
Assignment Deadline: Monday 23/5 23:59 Assignment-6 Context-free languages.

[top]

Week 8

Lecture Monday 23/5
13:15--15:00, HB3 		Ana Bove Slides-15 Turing machines. Summary of the course.
Lecture/
Exercise		 Thursday 26/5
13:15--15:00, HB3		 Ana Bove Exam 130528 (with solution),
Exam 130821 (with solution)		 Old exams
Exercises Monday 23/5
15:15--17:00, EA		 Andrea Exercise-7 Turing Machines.
  Tuesday 24/5
10:00--11:45, EA		 Marco
Consultation Wednesday 25/5
15:15--17:00, EL41		 Ana Bove
Assignment Deadline: Friday 27/5 23:59 Assignment-7 Turing Machines.

[top]