Plan for the Lectures, Exercise Sessions and Assignments

Finite Automata Theory and Formal Languages

TMV026/DIT321, LP4 2011

[Main page]

Lectures: Mondays 13:15--15:00 in HA2 and Tuesdays 10:00--11:45 in HC3.
Extra lecture only the first week: Thursday 10:00-11:45 in HA3.
Exercise sessions: Thursdays 13:15--15:00 in EB.

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 1

Lectures Monday 21/3 Slides Organisation and overview of the course
  Tuesday 22/3 Slides Formal proofs, inductively defined sets, proofs by (structural) induction
Sections 1.2--1.4 in the book
  Thursday 23/3 Slides Central concepts of automata theory, DFA
Sections 1.5, 2--2.2
Exercises Thursday 24/3 Text Formal proofs, alphabets and words
Assignment Deadline: Thursday 31/3 Text Formal proofs

Week 2

Lectures Monday 28/3 Slides DFA, NFA, subset construction algorithm
Sections 2.3--2.3.5
  Tuesday 29/3 Slides Equivalence between DFA and NFA, NFA with epsilon transitions
Sections 2.3.5--2.5.3
Exercises Thursday 31/3 Text DFA. NFA, NFA with epsilon transitions
Some exercises should be done in week 3.
Assignment Deadline: Thursday 7/4 Text DFA and NFA

Week 3

Lectures Monday 4/4 Slides NFA with epsilon transitions, regular expressions
Sections 2.5.4--2.5.5, 3--3.2.1, 3.4
  Tuesday 5/4 Slides Equivalence between AF and RE, Pumping Lemma for RL
Sections 3.2.2--3.2.3, 4--4.1
Exercises Thursday 7/4 Text Regular expressions
Some exercises should be done in week 4.
Assignment Deadline: Thursday 14/4 Text Epsilon-NFA, RE

Week 4

Lectures Monday 11/4 Slides Closure and decision properties of regular languages
Sections 4.2--4.3
  Tuesday 12/4 Slides Equivalence of RL, minimisation of automata
Section 4.4
Exercises Thursday 14/4 Text Properties of RL, minimisation of automata
Assignment Deadline: Thursday 5/5 Text Regular languages

Easter Break

Week 5

Lectures Monday 2/5 Slides Context free grammars, derivations, parse trees
Sections 5--5.2
  Tuesday 3/5 Slides Ambiguous grammars, Chomsky hierarchy
Section 5.4
  Thursday 5/5 10-12 ES51 Extra consultation class, please come with questions to discuss!!
Exercises Thursday 5/5 Text Context free grammars
Assignment Deadline: Thursday 12/5 Text Context free grammars

Week 6

Lectures Monday 9/5 Slides Normal forms and Pumping lemma for CFG
Section 7--7.2
  Tuesday 10/5 Slides Properties of CFG
Sections 7.3--7.4
Exercises Thursday 12/5 Text Context free languages
Assignment Deadline: Thursday 19/5 Text Context free languages

Week 7

Exercises Monday 16/5 Exams
Solving old exams (you may skip exercise 13 of the first exam)
Ignore the comments on derivatives in the solutions since we have not covered that
  Tuesday 17/5   Consultation and exercise class
Lecture Thursday 19/5 Slides Cancelled! Turing machines, Push-down automata, summary of the course
Sections 8