Finite Automata and Formal Languages - 2009 — LP4 2009


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

This course uses Introduction to Automata Theory, Languages, and Computation. by Hopcroft, Motwani and Ullman


Tuesday 10.00 - 11:15 in HA2 and Thursday 13:15 - 15:00 in HA2.
Exercice Sessions
Monday 13:15-15:00 in EC.

Plan for the lectures

Week Tuesday Thursday Chapters Topics Exercises
1 17 March -- 1.1, 1.2 Introduction, Proof by induction Week 1
2 24 March 26 March DFA and NFA Week 2
3 31 March 2 April NFA and regular expressions Week 3
4 21 April 23 April Regular expressions, abstract states Week 4
5 28 April -- Minimalization and pumping lemma Week 5
6 5 May -- Context-Free Grammar Week 6
7 12 May 14 May Context-Free Grammar Week 7
8 19 May -- Week 8


No books or written help during the exam.

Interesting links


Feel free to contact Thierry Coquand, Harald Hammarström 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.