Automata and Formal Languages 2011/12

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. Notice 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 initial version has already been revised several times, but it may still contain typos or mistakes. The current version of the script will always be here. If there is some important change then I will call your attention to it through the News.
  
  
• Here you can find an online collection of examples. It is rather outdated, it was written for an old version of the script.

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.

Slides

Last year I produced slides for the course. Here they are :

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

This year I will revise the slides during the course. I will try to provide the revised version in advance. The slides that I have revised so far will be available here:

• Automata classes and conversions
• Minimization
• Implementing operations on sets
• Implementing operations on relations
• Pattern matching
• Fixed-length languages
• Verification
• Monadic Second-order Logic
• Presburger Arithmetic
• Omega-automata
• Implementing boolean operations
• Emptiness checking
• 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.