104.458 AKINF: Automata and Formal Languages
This course is in all assigned curricula part of the STEOP.
This course is in at least 1 assigned curriculum part of the STEOP.

2021S, VO, 2.0h, 3.0EC


  • Semester hours: 2.0
  • Credits: 3.0
  • Type: VO Lecture
  • Format: Distance Learning

Learning outcomes

After successful completion of the course, students are able to...

The intended learning outcome of this course is to understand the contents of the course. Among other effects, this understanding forms the basis for the capability to correctly reproduce the statements and notions covered in the course as well as for the ability to explain and apply the proof techniques used in the course.

Subject of course

Automata theory is a central subject of theoretical computer science. Finite automata are the simplest possible machines and they appear explicitely as well as implicitely in a variety of different subjects and applications in both computer science and mathematics.

In mathematics, automata and formal languages are firmly tied to monoids and semirings. In this course we will first develop classical automata theory on the basis of continuous semirings. This leads to the more general notion of weighted automaton, as well as to corresponding generalisations of formal languages, grammars, etc. in a natural way. In the second part of the course we will deal with the classification of regular languages by properties of their syntactic monoids. As one of the most important results of this kind we will prove the theorem of Schützenberger (the characterisation of the star-free languages by aperiodic monoids).

Teaching methods

reading of lecture notes, discussion on contents

Mode of examination


Additional information

For further information please consult the TUWEL-page of this course.



Course dates

Fri13:00 - 14:0005.03.2021 Zoom (LIVE)Vorbesprechung

Examination modalities

Oral Exam

Course registration

Begin End Deregistration end
12.02.2021 00:00

Registration modalities

Melden Sie sich bitte zu dieser LVA an um auf den zugehörigen TUWEL-Kurs zugreifen zu können.



Course notes will be made available.

Previous knowledge

Knowledge of the elementary theory of formal languages (as taught in the course 108.036 "Theoretical Computer Science") is helpful.

Accompanying courses


if required in English