Description
The course provides an introduction to formal languages and automata
theory.
Schedule
| week |
date |
topics |
slides |
solutions |
|---|
| 01 |
05.10 & 09.10 |
deterministic finite automata, closure properties |
pdf (x1, x4) |
pdf |
| 02 |
12.10 & 23.10 |
nondeterministic finite automata, ϵ-transitions, closure properties |
pdf (x1, x4) |
pdf |
| 03 |
19.10 & 30.10 |
regular expressions, homomorphisms |
pdf (x1, x4) |
pdf |
| 04 |
02.11 & 06.11 |
|
|
pdf |
| 05 |
09.11 & 13.11 |
state minimization, Myhill-Nerode relations |
pdf (x1, x4) |
pdf |
| 06 |
16.11 & 20.11 |
derivatives, Kleene algebra, equivalence of regular expressions |
pdf (x1, x4) |
pdf |
| 07 |
23.11 & 27.11 |
equivalence of finite automata, context-free grammars, ambiguity |
pdf (x1, x4) |
pdf |
| 08 |
30.11 & 04.12 |
Chomsky normal form, pumping lemma, CKY algorithm |
pdf (x1, x4) |
pdf |
| 09 |
07.12 & 11.12 |
Ogden's lemma, pushdown automata, closure properties |
pdf (x1, x4) |
pdf |
| 10 |
14.12 & 18.12 |
Turing machines, diagonalization |
pdf (x1, x4) |
pdf |
| 11 |
04.01 & 08.01 |
|
|
pdf |
| 12 |
11.01 & 15.01 |
diagonalization, reduction |
pdf (x1, x4) |
pdf |
| 13 |
18.01 & 22.01 |
reduction, Rice's theorem, unrestricted grammars |
pdf (x1, x4) |
pdf |
| 14 |
25.01 & 29.01 |
Rice's theorem, Post correspondence problem |
pdf (x1, x4) |
pdf |
|
01.02 |
1st exam
solution |
|
|
|
25.02 |
2nd exam
solution |
|
|
|
27.09 |
3rd exam
solution |
|
|
Literature
The course is largely based on the following book:
Slides as well as solutions to selected exercises will be made available
online.
Further Reading
Numerous other books exist that cover more or less the same material. The
following are recommended:
-
John E. Hopcroft, Rajeev Motwani and Jeffrey D. Ullman,
Introduction to Automata Theory, Languages, and Computation (3rd
edition),
Addison Wesley, 2007,
ISBN 9780321462251
-
Elaine Rich,
Automata, Computability, and Complexity, Pearson Education, 2008,
ISBN 9780132288064