Kurzbeschreibung

Formale Sprachen und Automatentheorie

- Kurzbeschreibung -

Aufbauend auf dem Modul Theoretische Grundlagen der Informatik wird die Theorie der Chomsky-Sprachklassen und der zugehörigen Automatenbegriffe behandelt, wobei der Schwerpunkt auf regulären und kontextfreien Sprachen liegt.

Für kontextfreie Sprachen lernen die Studenten Chomsky-2-Grammatiken und Kellerautomaten als Beschreibungsmitel kennen. Es werden Normalformen für Grammatiken und der CYK-Algorithmus vorgestellt.

Die in Theoretische Grundlagen der Informatik gewonnenen Grundkenntnisse über reguläre Sprachen werden vertieft und ergänzt. Themen sind insbesondere reguläre Ausdrücke und die Konstruktion von Minimalautomaten.

Für beide Sprachklassen werden Eigenschaften der Sprachklassen und ihrer Elemente behandelt, zum Beispiel das Pumping-Lemma für kontextfreie Sprachen und der Satz von Myhill-Nerode.