Plan for the Lectures, Exercise Sessions and Assignments

Finite Automata Theory and Formal Languages

TMV026/DIT321, LP4 2012

[Main page]

Lectures Mondays 13:15--15:00 and Tuesdays 10:00--11:45, all weeks but week 6
Thursdays 10:00--11:45, only weeks 1 and 6
See below for information about the rooms.
Exercise session Thursdays 13:15--15:00, in EF all weeks but weeks 2 and 8
On week 2 the room is HC3.
On week 8 there is no exercise class.
Consultation time Thursdays 10:00--11:45 in group room 5205, all weeks but weeks 1 and 6

See link at Time Edit for 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 will be updated during the running of the course to take into account possible deviations.

Week 1

Lectures Monday 12/3 HC4 Slides-1 Organisation and overview of the course
  Tuesday 13/3 HA2 Slides-2 Formal proofs, inductively defined sets, proofs by (structural) induction
Sections 1.2--1.4 in the book
  Thursday 15/3 EA Slides-3 Central concepts in discrete mathematics and automata theory
Section 1.5
Exercise Thursday 15/3 EF Ex-1 Formal proofs, alphabets and words
Assignment Deadline: Thursday 22/3 Ass-1 Formal proofs


Week 2

Lectures Monday 19/3 HC3 Slides-4 DFA
Sections 2--2.2
  Tuesday 20/3 EC Slides-5 NFA, subset construction algorithm, equivalence between DFA and NFA
Sections 2.3--2.3.5
Consultation Thursday 22/3 5205
Exercise Thursday 22/3 HC3 Ex-2 DFA, NFA, NFA with epsilon transitions
Some exercises should be done in week 3.
Assignment Deadline: Thursday 29/3 Ass-2 DFA and NFA


Week 3

Lectures Monday 26/3 EB Slides-6 NFA, NFA with epsilon transitions
Sections 2.3.6--2.5.5
  Tuesday 27/3 EC Slides-7 Regular expressions, from FA to RE
Sections 3--3.1, 3.4, 3.2.2
Consultation Thursday 29/3 5205
Exercise Thursday 29/3 EF Ex-3 Regular expressions
Some exercises should be done in week 4.
Assignment Deadline: Thursday 19/4 Ass-3 Epsilon-NFA, RE


Easter Break

Week 4

Lectures Monday 16/4 EB Slides-8 From RE to FA, pumping Lemma for RL, closure properties of regular languages
Sections 3.2.3, 4--4.2.1
  Tuesday 17/4 EC Slides-9 Closure and decision properties of regular languages.
Sections 4.2.2--4.3
Consultation Thursday 19/4 5205
Exercise Thursday 19/4 EF Ex-4 Properties of RL, minimisation of automata
Some exercises should be done in week 5.
Assignment Deadline: Thursday 26/4 Ass-4 Regular languages


Week 5

Lectures Monday 23/4 EB Slides-10 Equivalence of RL, minimisation of automata
Section 4.4
  Tuesday 24/4 EC Slides-11 Context free grammars, derivations, parse trees
Sections 5--5.2
Consultation Thursday 26/4 5205
Exercise Thursday 26/4 EF Ex-5 Context free grammars
Some exercises should be done in week 6.
Assignment Deadline: Monday 7/5 Ass-5 Context free grammars


Week 6

Lecture Thursday 3/5 EA Slides-12 Ambiguous grammars, Chomsky hierarchy
Section 5.4
Exercise Thursday 3/5 EF Same as week 5 Context free grammars


Week 7

Lecture Monday 7/5 EB Slides-13 Normal forms and Pumping lemma for CFL
Section 7--7.2
  Tuesday 8/5 EC Slides-14 Closure and decision properties of CFL
Sections 7.3--7.4
Consultation Thursday 10/5 5205
Exercise Thursday 10/5 EF Ex-6 Context free grammars and languages
Assignment Deadline: Monday 14/5 Ass-6 Context free languages


Week 8

Lecture Monday 14/5 EB Slides-15 Turing machines, Push-down automata, summary of the course
Section 8
Exercise Tuesday 15/5 EC Exam 100527, Exam 100827
Older exams (you may skip exercise 13 of the first exam) and some solutions (ignore the comments on derivatives in the solutions since we have not covered that)