Automata and Formal Languages 2020/21

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