Automata and Formal Languages 2013/14

News | Dates | Grading | Content | Exercises | Exam | Material

This lecture requires basic knowledge in automata theory, e.g., obtained during the course 'Einführung in die theoretische Informatik'. A detailed description of the contents can be found in the lecture notes. Here is an outline:

Automata on finite words

1. Automata classes and conversions
   • Regular expressions, deterministic and nondetermistic automata, finite monoids
   • Conversion algorithms
2. Algorithms for automata
   • Word problem
   • emptiness
   • Powerset construction
   • Product automaton
   • Minimizing DFAs (Moore's algorithm, Hopcroft's algorithm, Brzozowski's algorithm)
   • Hopcroft-Karp equivalence test
3. Angluin's L*-learning algorithm
4. Presburger arithmetic
5. Automata and logic

Automata on infinite words

1. Automata classes and conversions
   • Omega-regular expressions
   • Büchi, Rabin, Streett, Muller, and parity automata
   • recognition by finite semigroups
   • strongly unambiguous Büchi automata (aka Carton-Michel automata)
2. Boolean operations
   • Union and intersection
   • Complementation (Ramsey based, Klarlund's construction)
3. Emptiness check
4. Equivalence
5. Safra's construction
6. deterministic automaton models
7. topological properties