Automata and Formal Languages 2017/18

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
   • Conversion algorithms
2. Minimization and reduction
   • Minimizing DFAs
   • Reducing NFAs
3. Boolean operations and tests
   • Implementation on DFAs
     • Membership, complement, union, intersection, emptiness, universality, inclusion, equality.
   • Implementation on NFAs
     • Membership, complement, union, intersection, emptiness, universality, inclusion, equality.
4. Operations on relations
   • Projection, join, post, pre.
5. Operations on finite universes: decision diagrams.
6. Automata and logic
7. Applications: pattern-matching, verification, Presburger arithmetic

Automata on infinite words

1. Automata classes and conversions
   • Omega-regular expressions
   • Büchi, Streett, and Rabin automata
2. Boolean operations
   • Union and intersection
   • Complement
3. Emptiness check
4. Applications: verification using temporal logic