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
