# Finite Automata and Formal Languages - 2009 — LP4 2009

## News

• (19 May) Harald has written some solutions of the test exam

• (15 May) I added a small explanation of the pumping lemma for context-free languages (correcting one question for the exam 2 below)

• (4 May) The lecture on Thursday 7 May is cancelled.

• (23 April) The students representative are Mikael Danell and Mikael Tonnberg. The suggestions of the meeting today were the following. The slides should be available before the lectures, as well as the exercises and what chapters are to be covered so that one can know what to read a week ahead. Old exams should be made available. Otherwise, the level of the course is appropriate. Maybe one should have mandatory exercises each week. It will also be nice with an extra exercise session.

• (25 March) I have tried to explain in the following note the two definitions of the transition function on strings (definition 2.2.4 in the book and why they are equivalent (exercises 2.2.2 and 2.2.3)

## 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

## Schema

Lectures
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

## Exam

No books or written help during the exam.

## 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.

• The seminal paper of McCulloch and Pitts on neural networks

• The seminal paper of Rabin and Scott

• Regular expression matching can be simple and fast A text by Russ Cox presenting Ken Thompson's algorithm. See also here for a very short description of an implementation in Haskell

## Communications

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.