Finite Automata and Formal Languages
lp 4 2006


The last exam with its solution can be found here

A past exam can be found here (notice however that it was for a 3 point course. There will be more questions involving proving properties in the exam this year.)

The following slides of Robert Keller present clearly the proof of the Pumping Lemma for CFLs, and Myhill-Nerode theorems for regular languages.

The following advices for how to write the homework may be relevant

Goals of the course

Finite automata are basic mathematical models of some physical systems. The theory of finite automata is fundamental in computer sciences. Besides having direct concrete applications, it is mathematically simple and elegant. It provides ideal illustrations of basic notions in mathematics (set theory, proof by induction).

The main applications in the text book (besides a mathematical model of a protocol) are about text search, lexical analysis and parsing. Other kind of applications (model of vending machines, traffic signals, etc...) require the notion of finite state transducers (Mealy machines), whose theory is almost identical to the one of finite automata.

Text Book

The text book is ``Introduction to Automata Theory, Languages, and Computation'' by Hopcroft, Motwani and Ullman


Tuesday 10.00 - 11.45 i HB1 and thursday 10.00 - 11.45 i HB3 (except 6th April and 11th May)
Exercice Sessions
Will start Week 2. If one participates in exercice sessions and solve the homeworks, one can get some bonus points.

Plan for the lectures

Week Tuesday Thursday Chapters Topics Exercices
1 14 March 16 March 1,2.2 Introduction. Languages. Inductive Proofs. DFA. Products of DFA. Week 1
2 21 March 23 March 2.2,2.3,2.4,2.5,3.1,3.2 NFA. Power set construction. Regular Expressions. Week 2
3 28 March 30 March 3.3,3.4,4.1,4.2 Algebraic Laws. Pumping Lemma. Closure Properties. Week 3
4 4 April - 4.3,4.4 Decision Properties. Minimization. Week 4
5 25 April 27 April 5 Myhill-Nerode theorem, Mealy machines and Context-Free Grammars. Week 5
6 2 May 4 May 6 Properties of Context-Free Languages Week 6
7 9 May - 7 Pumping Lemma for CFL and CYK algorithm Week 7
8 - 18 May 7 Repetition Week 8

Interesting links

A general introduction with a clear presentation of different ways to represent FA (functional, imperative, feedback system). This is an extract of a book by Robert Keller.


Feel free to contact Thierry Coquand, Samuel Bengmark in case you have any questions or problems. Almost everything you get in the class is available electronically. Send me a request if you have missed some stuff.