en | de

Formal Language and Automata Theory

master program

VO2 + PS1  WS 2020/2021  703603 + 703604


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: