Reguläre und kontextfreie Sprachen
Vorlesung im Wintersemster 2013/2014
Inhalt
Die Vorlesung richtet sich an M.Sc. Studenten. Sie bietet ein tieferes Verständnis für die zwei essentiellen Sprachklassen, die die Basis für viele Bereiche der Informatik bilden, die regulären und die kontextfreien Sprachen. Auch wenn einige der gezeigten Ergebnisse bereits seit längerem existieren, haben sie nicht an Bedeutung verloren. Darüber hinaus sind einige der ältesten Probleme der Theoretischen Informatik hier zu finden.
Anwendungen werden angesprochen, aber der Schwerpunkt liegt in der Theorie, in diesen beiden Themen: Zum einen der alternative Beschreibung von Sprachen mit verschiedenen Rahmenwerken und zum anderen der Klassifikation von Sprachen mit dem Sicht auf Komplexität. Die Vorlesung wird in deutsch gehalten, wenn dies bevorzugt wird.
Struktur des Kurses:
Teil I: Reguläre Sprachen
- Sern-Höhe und das Stern-Höhe Problem
- Sternfreie Sprachen, Logik erster Ordnung und der Satz von Schützenberger
- Reguläre Sprachen und Kreislauf Komplexität
Teil II: Kontextfreie Sprachen
- Chomsky-Schützenberger Theorem
- Generatoren für kontextfreie, lineare, und 1-Zählersprachen
- Deterministische kontextfreie Sprachen
Voraussetzungen
Kenntnisse in der Automatentheorie durch die Basiskurse ist notwendig. Wissen aus weiterführenden Vorlesungen wie „Angewandte Automatentheorie oder „Infinite Computations“ ist hilfreich.
Lernmaterial
Das Lernmaterial ist im L2P Lernraum verfügbar. Bitte schreiben sie sich für die Vorlesugn ein um Zugriff zu erhalten.
Organisation
Die Vorlesung wird in Englisch gehalten.
Dozent