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.

2019S, VO, 2.0h, 3.0EC

Properties

  • Semester hours: 2.0
  • Credits: 3.0
  • Type: VO Lecture

Aim of course

Advanced knowledge of the theory of automata and formal languages

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).

Lecturers

Institute

Course dates

DayTimeDateLocationDescription
Fri14:15 - 15:4508.03.2019 - 28.06.2019 Dissertantenraum (Freihaus, 8. Stock, grüner Bereich)Vorlesung
AKINF: Automata and Formal Languages - Single appointments
DayDateTimeLocationDescription
Fri08.03.201914:15 - 15:45 Dissertantenraum (Freihaus, 8. Stock, grüner Bereich)Vorlesung
Fri15.03.201914:15 - 15:45 Dissertantenraum (Freihaus, 8. Stock, grüner Bereich)Vorlesung
Fri22.03.201914:15 - 15:45 Dissertantenraum (Freihaus, 8. Stock, grüner Bereich)Vorlesung
Fri29.03.201914:15 - 15:45 Dissertantenraum (Freihaus, 8. Stock, grüner Bereich)Vorlesung
Fri05.04.201914:15 - 15:45 Dissertantenraum (Freihaus, 8. Stock, grüner Bereich)Vorlesung
Fri12.04.201914:15 - 15:45 Dissertantenraum (Freihaus, 8. Stock, grüner Bereich)Vorlesung
Fri03.05.201914:15 - 15:45 Dissertantenraum (Freihaus, 8. Stock, grüner Bereich)Vorlesung
Fri10.05.201914:15 - 15:45 Dissertantenraum (Freihaus, 8. Stock, grüner Bereich)Vorlesung
Fri17.05.201914:15 - 15:45 Dissertantenraum (Freihaus, 8. Stock, grüner Bereich)Vorlesung
Fri24.05.201914:15 - 15:45 Dissertantenraum (Freihaus, 8. Stock, grüner Bereich)Vorlesung
Fri07.06.201914:15 - 15:45 Dissertantenraum (Freihaus, 8. Stock, grüner Bereich)Vorlesung
Fri14.06.201914:15 - 15:45 Dissertantenraum (Freihaus, 8. Stock, grüner Bereich)Vorlesung
Fri21.06.201914:15 - 15:45 Dissertantenraum (Freihaus, 8. Stock, grüner Bereich)Vorlesung
Fri28.06.201914:15 - 15:45 Dissertantenraum (Freihaus, 8. Stock, grüner Bereich)Vorlesung

Course registration

Not necessary

Curricula

Literature

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 recommended.

Accompanying courses

Language

if required in English