Kurzbeschreibung

Formale Sprachen und Automatentheorie

- Kurzbeschreibung -

Gegenstand dieser Vorlesung ist die Theorie der Chomsky-Sprachklassen und der zugehörigen Automatenbegriffe, wobei der Schwerpunkt auf regulären und kontextfreien Sprachen liegt.

Inhalte sind insbesondere:

Die Hierarchie der Chomsky-Sprachklassen: Grammatikklassen und Akzeptoren, Abschlußeigenschaften
Reguläre Sprachen: Chomsky-3-Grammatiken, deterministische und nichtdeterministische endliche Automaten, reguläre Ausdrücke, Konstruktion von Minimalautomaten, Satz von Myhill-Nerode, Pumping-Lemma für reguläre Sprachen, Entscheidbarkeitsfragen
Kontextfreie Sprachen: Chomsky-2-Grammatiken, Kellerautomaten, Umformungen für Grammatiken und Normalformen (insbesondere Chomsky-Normalform und Greibach-Normalform), Pumping-Lemma für kontextfreie Sprachen, CYK-Algorithmus, Entscheidbarkeitsfragen