# Weekly Plan for the Lectures, Exercise Sessions and Assignments

## Finite Automata Theory and Formal Languages

### TMV027/DIT321, LP4 2014

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 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 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     Exercise 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. Thursday 20/3 10:00--11:45, HC3 Simon Huber Recap Exercises Logic, sets, relations and functions. Deadline: Sunday 30/3 23:59 Assignment-1 Formal proofs.

[top]

### Week 2

Lectures   Exercises 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. 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 Wednesday 26/315:15--17:00, ES51 Ana Bove Deadline: Sunday 6/4 23:59 Assignment-2 DFA and NFA.

[top]

### Week 3

Lectures   Exercises 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. 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 Wednesday 2/4 15:15--17:00, ES51 Ana Bove Deadline: Sunday 13/4 23:59 Assignment-3 Epsilon-NFA, RE.

[top]

### Week 4

Lectures   Exercises 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. Tuesday 8/4 10:00--11:45, EF Inari Listenmaa Exercise-3 Regular expressions. Thursday 10/4 10:00--11:45, EB Simon Huber Wednesday 9/4 15:15--17:00, ES51 Ana Bove Deadline: Sunday 4/5 Monday 5/5 23:59 Assignment-4 Regular languages.

[top]

### Week 5

Lectures Exercise 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. 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! Wednesday 30/4 13:15--15:00, ES51 Ana Bove NEW!

[top]

### Week 6

Lecture   Exercise 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. 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 Wednesday 7/5 15:15--17:00, ES51 Ana Bove Deadline: Monday 12/5 23:59 Assignment-5 Context free grammars.

[top]

### Week 7

Lecture   Exercise 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. 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 Wednesday 14/5 15:15--17:00, ES51 Ana Bove Deadline: Monday 19/5 23:59 Assignment-6 Context free languages.

[top]

### Week 8

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

[top]