(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)
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.
This course uses Introduction to Automata Theory, Languages, and Computation. by Hopcroft, Motwani and Ullman
| 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.
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
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.