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