This course is taught in English. This course is regularly offered every summer semester. This course was offered in the summer semester 2022, and the summer semester 2023.

Link to official course page

Format

This course consists of weekly lectures and weekly tutorials. Student performance is evaluated by a written exam (90 minutes) during the exam period. The overall grade can be raised by obtaining a 20% bonus from individually solving weekly assignment sheets.

The course load is 6 ECTS.

Description

Automata and formal languages are classic topics in theoretical computer science. Automata are often classified by the class of formal languages they can recognize, as in the Chomsky hierarchy, which describes a nesting relationship between languages. The Chomsky hierarchy provides the overarching theme of this course, in which the following topics are treated:

• Basics of automata and formal languages
• The Chomsky hierarchy
• Deterministic finite automata, definition and construction
• Regular languages, closure properties, word problem, string matching
• Nondeterministic automata: Rabin-Scott transformation of nondeterministic into deterministic automata
• Epsilon automata, minimization of automata, elimination of e-edges, uniqueness of the minimal automaton (modulo renaming of states)
• Myhill-Nerode Theorem: Correctness of the minimization procedure, equivalence classes of strings induced by automata
• Pumping Lemma for regular languages: provision of a tool which, in some cases, can be used to show that a finite automaton principally cannot be expressive enough to solve a word problem for some given language
• Regular expressions vs. finite automata: Equivalence of formalisms, systematic transformation of representations, reductions
• Pushdown automata and context-free grammars: Definition of pushdown automata, definition of context-free grammars, derivations, parse trees, ambiguities, pumping lemma for context-free grammars, transformation of formalisms (from pushdown automata to context-free grammars and back)
• Chomsky normal form
• CYK algorithm for deciding the word problem for context-free grammrs
• Deterministic pushdown automata
• Deterministic vs. nondeterministic pushdown automata: Application for parsing, LL(k) or LR(k) grammars and parsers vs. deterministic pushdown automata, compiler compiler
• Regular grammars: Turing machines and linear bounded automata vs general and context-sensitive grammars
• Turing machines
• Halting problem

Provided course materials

- Lecture slides
- Lecture recordings
- Assignment sheets
- Simulator software

Recommended literature

• John E. Hopcroft, Rajeev Motwani, Jeffrey D. Ullman: Introduction to Automata Theory, Languages, and Computation. Pearson, 3rd edition, 2006
• Uwe Schöning: Logik für Informatiker. Spektrum, 5th edition, 2000
• Martin Kreuzer, Stefan Kühling: Logik für Informatiker. Pearson Studium, 2006
• Gottfried Vossen, Kurt-Ulrich Witt: Grundkurs Theoretische Informatik, Vieweg-Verlag, 2010.
• Christel Baier, Joost-Pieter Katoen: Principles of Model Checking, The MIT Press, 2007