Automata and Formal Languages 2010/11

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

Lecture notes

• Access requires a username and password that will be announced in the first lecture.
  
  The initial version of the notes can be found here. The initial version may contain minor errors that will be corrected during the course. The current version of the script will always be here .
  
  
• Here you can find an online collection of examples. It is a bit outdated, it was written for the old version of the script.

Slides

Due to a student's request I am making the slides available. As explained at the last lecture, the slides are just excerpts from the lecture notes. I prepare them ad hoc, and only shortly before the lecture. They are not designed carefully, and I do not recommend at all to prepare the exam from them! Access requires the same username and password as above.

• Automata classes and conversions
• Minimization
• Implementing operations on sets
• Implementing operations on relations
• Presburger Arithmetic
• Fixed-length languages
• Monadic Second-order Logic
• Pattern matching
• Verification
• Omega-automata
• Implementing boolean operations
• Emptiness checking
• Verification of liveness properties

Literature

• Tobias Nipkow's slides from his introductory lecture (in German).
• 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.

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.