I7 Logo
Chair for Foundations of Software Reliability and Theoretical Computer Science
Informatik Logo TUM Logo
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