I7 Logo
Chair for Foundations of Software Reliability and Theoretical Computer Science
Informatik Logo TUM Logo
Automata and Formal Languages 2009/10

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


  • The initial version of the script (20.10.2009) can be found here.

    The initial version may contain minor errors that will be corrected during the course. The current version of the script is here .

    The material on automata on infinite words can be found here .

    Access requires a username and password that were announced in the first lecture.

  • An online collection of examples.



  • John E. Hopcroft, Rajeev Motwani, Jeffrey D. Ullman;
    Introduction to Automata Theory, Languages and Computation;
    Addison-Wesley Longman, 3rd edition, 2006.
  • 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.


In both exercises and class we will use a number of tools to demonstrate the practical usefulness of the theory and to present typical applications. Here is a list of tools to be used.
  • SPIN: to illustrate Büchi automata
  • MONA: to illustrate WS1S and corresponding automata
  • LTL2BA: translating LTL formulas to Büchi automata
  • Uppaal: to play with timed automata