This module is taught in English. This module is regularly offered every summer term.

This module was previously offered in the summer terms 2022 and 2023.

Description

Automata and formal languages are classic topics in theoretical computer science, related to mathematical logic. Automata are abstract machines to solve computational problems, by automatically executing a predetermined sequence of steps. Automata can thus also be seen as finite representations of formal languages, which model computational problems and may be infinite. Formal languages are classified according to the Chomsky hierarchy, which provides the overarching theme of this module. In turn, formal languages are generated by grammars, which are the third major object (next to automata and formal languages) which are studied in this module. We will study the theories which link these three objects, and study their important roles in fundamental applications such as compiler construction, formal verification, and parsing in natural and computer languages.

Recommended prerequisites

We expect attendees to be proficient in the material from the following modules:

• Discrete Algebraic Structures
• Mathematics I
• Mathematics II

We further recommend basic knowledge of the following topics:

• Programming in Python, C++, C# or Java

Learning goals

In this module you will learn

• to design automata for specific tasks,
• to design formal languages and classify them according to the Chomsky hierarchy,
• to link specific automata, formal languages and grammars in terms of their expressive power,
• to model computational problems and decide the (non-)existence of finite algorithms for their solution.

Topics

In this module we will cover the following topics:

• 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

Setup

• Weekly lectures (in presence) and weekly tutorial session (in presence).
• Each week an assignment is handed out, which should be solved individually outside the classroom  and then be submitted for grading. The assignment and its solutions are then discussed in the subsequent tutorial session. If sufficiently many points are awarded in the grading process (cumulative over all assignments of the term), then a bonus is given for the final exam at the end of the term.
• Final exam (written) for 90 minutes at the end of the term, whose outcome (together with a potential bonus from the assignment) determines the final grade for the module.

Overall module load: 6 ETCS credit points.

Provided 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