Nach positiver Absolvierung der Lehrveranstaltung sind Studierende in der Lage...

Das intendierte Lernergebnis dieser LVA besteht darin den Inhalt der LVA zu verstehen. Dieses Verständnis bildet unter anderem die Basis für die Fähigkeit die in der LVA besprochenen Aussagen und Begriffe korrekt wiederzugeben, sowie dafür die in der LVA eingesetzten Beweismethoden erklären und anwenden zu können.

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

Vorlesung

Mündliche Prüfung

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