Weiterführende Kenntnisse der Theorie der Automaten und formalen Sprachen

Die Automatentheorie ist ein zentrales Gebiet der theoretischen Informatik.
Endliche Automaten sind die einfachsten theoretischen Maschinen und sie treten
explizit und implizit in einer Vielzahl von Gebieten und Anwendungen sowohl in
der Informatik als auch in der Mathematik auf.

Als Teilgebiet der Mathematik hängt die Automatentheorie eng mit der Algebra,
insbesondere mit Monoiden und Halbringen zusammen. In dieser Vorlesung wird
zunächst die klassische Automatentheorie auf Basis von stetigen Halbringen neu
entwickelt. Das führt auf natürliche Weise zum allgemeineren Begriff des
gewichteten Automaten und entsprechenden Verallgemeinerungen von formalen
Sprachen, Grammatiken, etc. Im zweiten Teil der Vorlesung beschäftigen wir uns
mit der Klassifizierung regulärer Sprachen durch Eigenschaften ihrer
syntaktischen Monoide. Als eines der wichtigsten Resultate dieser Art werden
wir den Satz von Schützenberger beweisen (die Charakterisierung der sternfreien
Sprachen durch aperiodische Monoide).

Es wird ein Skriptum zur Verfügung gestellt werden.

Kenntnis der elementaren Theorie formaler Sprachen (wie sie z.B. in der LVA 108.036 "Theoretische Informatik" vermittelt wird) ist empfohlen.