Automata and Formal Languages 2009/10

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

Slides/Script

• 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.

Handouts

• Tobias Nipkow's slides from last term's introductory lecture (in German).
• Deepak D'Souza's handout on monadic second order logic over words and Büchis's theorem about the equivalence of regularity and MSO-definability.
• Madhavan Mukund: Finite-state Automata on Infinite Inputs.
• The material on timed automata.

Literature

• 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.

Tools

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