Updates

Schedule for November (changes in bold):

• We will have lectures on 2.11, 6.11, 7.11, 14.11, 20.11, 21.11, 23.11, 27.11, and 28.11.

• We will have tutorials on 9.11, 13.11, 16.11, and 30.11.

The slots are in their usual rooms, i.e. Mondays and Tuesdays we meet in HS2, and Thursdays in 02.13.010.

Moodle page

There is a Moodle page, but we do not plan to use it.

Contact

The teaching assistant for this course is Philipp Czerner. There is a public channel on Zulip for questions. For private matters, you can contact me on Zulip or via e-mail.

Material

The open-access book “Automata Theory: An Algorithmic Approach” by Javier Esparza and Michael Blondin covers the topics of the lecture excellently. You can download it here.

To repeat the basics on automata that this course builds on, consider the (German) slides of the bachelor course „Einführung in die theoretische Informatik“, or the (German) recordings of the lecture. In English, there are Debasis Mitra's slides (and many others can be found online as well).

Slides

Exercise Sheets

You can also access the exercise sheets from the previous years, they are eerily similar.

Recordings

Also see the recordings from last year.

Books

• Javier Esparza. Michael Blondin
  Automata Theory: An Algorithmic Approach
  MIT Press, 2023.
• 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.

Exam

The final grade is determined by a written exam at the end of the term.

To prepare yourself for the exam, you are strongly encouraged to take some past exams at home. It is additionally encouraged to go through the exercise sheets.

Past exams