course: Automata Theory

teaching methods:
lecture with tutorials
handouts, Moodle
responsible person:
Prof. Dr. Thomas Zeume
Prof. Dr. Thomas Zeume (Mathematik)
offered in:
summer term

dates in summer term

  • lecture Tuesdays: from 10:00 to 12.00 o'clock


Die Angaben zu den Prüfungsmodalitäten (im WiSe 2020/2021 | SoSe 2021) erfolgen vorbehaltlich der aktuellen Situation. Notwendige Änderungen aufgrund universitärer Vorgaben werden zeitnah bekanntgegeben.

Date according to prior agreement with lecturer.

Form of exam:oral
Registration for exam:FlexNow


Students learn about different automata models that are used in computer science. They learn how models can be analysed with respect to closure properties and algorithmic properties. They shall develop an understanding o the power o distinct automata models, and be enabled to develop and analyse new automata models.


Automata play an important role in computer science and its applications. As an example, finite state automata as introduced in introductory courses on theoretical computer science, are used in compiler construction and in pattern matching for strings. In this course we systematically study the theoretical foundations of diverse automata models and establish connections of automata theory to other areas such as logic and algebra. Automata models have been developed for a plethora of applications, among other we will study

  • w-Automata: Very similar to finite state automata, these automata work on infinite words. They are used in formal verification of hardware and software.
  • Tree automata: Inputs for these automata are trees and they are used for instance in specification and querying of tree-shaped data, as for instance XML or JSON.
  • Probabilistic automata: These automata accept their inputs with certain probabilities and can be used in pattern recognition and formal verification.

The focus of this course is on theoretical properties of automata, but we will also consider some applications.

This is a course or students o mathematics, computer science and ITS. Knowledge rom an introductory theoretical computer science course is mandatory.