Reguläre und kontextfreie Sprachen

 

Vorlesung im Wintersemster 2014/2015

Kontakt

Telefon

work
+49 241 80 21710

E-Mail

E-Mail
 
 

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

  1. Sern-Höhe und das Stern-Höhe Problem
  2. Sternfreie Sprachen, Logik erster Ordnung und der Satz von Schützenberger
  3. Reguläre Sprachen und Kreislauf Komplexität


Teil II: Kontextfreie Sprachen

  1. Chomsky-Schützenberger Theorem
  2. Generatoren für kontextfreie, lineare, und 1-Zählersprachen
  3. 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

Wolfgang Thomas