Note: This is an archvied version of our old webpage. Some links might be broken. The current one can be found here.
I7 Logo
Chair for Foundations of Software Reliability and Theoretical Computer Science
Informatik Logo TUM Logo
Automata and Formal Languages 2018/19

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

Lecture notes

  • The lecture notes can be found here (Feb. 13, 2019). Note that some pages use color! Printed copies can be obtained from the Fachschaft at a very low price, if some student volunteers to organize the process.

    The lecture notes have already been revised several times, but they may still contain typos or mistakes. Please email me if you find some. If there is some important error then I will call your attention to it through the News.

  • Here you can find an online collection of examples. It is seriously outdated, it was written for an old version of the script.

Literature

  • My slides for the course Introduction to Theoretical Computer Science (in German), with the material on Automata Theory of which we assume knowledge (NFAs, DFAs, regular expressions, conversion algorithms, closure under boolean operations, pumping lemma, minimal DFAs).
  • Debasis Mitra's slides from his introductory lecture (in English). Remark: this is just one of the many sets of slides available on line.
  • John E. Hopcroft, Rajeev Motwani, Jeffrey D. Ullman;
    Introduction to Automata Theory, Languages and Computation;
    Addison-Wesley Longman, 3rd edition, 2006.
  • John Martin;
    Introduction to Languages and the Theory of Computation;
    McGraw-Hill, 2002.
  • Michael Sipser;
    Introduction to the Theory of Computation;
    Course Technology, 2005.
  • Joerg Flum, Erich Graedel, Thomas Wilke (eds.);
    Logic and Automata: History and Perspectives, Volume 2;
    Amsterdam University Press, 2008.
  • Dominique Perrin, Jean-Eric Pin;
    Infinite Words: Automata, Semigroups, Logic and Games;
    Academic Press, 2004.

Slides

  1. Introduction
  2. Automata as data structures
  3. Automata classes and conversions
  4. Minimization
  5. Implementing operations on sets
  6. Pattern matching
  7. Implementing operations on relations
  8. Fixed-length languages
  9. Verification
  10. Presburger Arithmetic
  11. Monadic second-order logic on words
  12. Omega-automata
  13. Implementing boolean operations
  14. Emptiness checking
  15. Verification of liveness properties

Tools

In both exercises and class we will demonstrate and use a number of tools to illustrate the theory and to present typical applications. They may include:
  • JFLAP. Automata on finite words
  • SPIN. Verification using automata on infinite words
  • MONA. Logic and automata connection.
  • LTL2BA. Automata and temporal logic.
  • GOAL. Büchi Automata and temporal logic, interactive graphical tool
  • JFLAP Game. A game for practicing automata, regular expression and temporal logic interconvertions.
  • Owl. A Java tool collection and library for Omega-words, ω-automata and Linear Temporal Logic (LTL). Batteries included.