| Formale Sprachen und Automatentheorie [2021 SoSe] | ||
|---|---|---|
| Code IFSA |
Name Formale Sprachen und Automatentheorie |
|
| LP 8 LP |
Dauer ein Semester |
Angebotsturnus mindst. jedes 4. Semester |
| Format Vorlesung 4 SWS, Übungen 2 SWS mit Hausaufgaben. |
Arbeitsaufwand 240 h; davon 90 h Präsenzstudium 60 h Prüfungsvorbereitung (und Prüfung) 90 h Selbststudium und Aufgabenbearbeitung (eventuell in Gruppen) |
Verwendbarkeit B.Sc. Angewandte Informatik, M.Sc. Angewandte Informatik |
| Sprache |
Lehrende |
Prüfungsschema |
| Lernziele | Die Studierenden kennen die Stufen der Chomsky-Hierarchie und deren äquivalente Beschreibung durch Grammatiken und Automatenmodelle, kennen die Charakterisierungen der Klasse der regulären Sprachen durch rechts- bzw. linkslineare Grammatiken, durch deterministische und nichtdeterministische endliche Automaten, durch reguläre Ausdrücke und durch Rechtskongruenzen mit endlichem Index, sind in der Lage, das Pumping-Lemma für reguläre Sprachen zu beweisen und dieses anzuwenden, um zu zeigen, dass bestimmte Sprachen nicht regulär sind, kennen den Nachweis der Eindeutigkeit des Minimalautomaten und können diesen in Form eines reduzierten Automaten oder eines Äquivalenzklassenautomaten konstruieren, können das Pumping-Lemma für kontextfreie Sprachen beweisen und dieses anwenden, um zu zeigen, dass bestimmte Sprachen nicht kontextfrei sind, können die Klasse der kontextfreien Sprachen durch kontextfreie Grammatiken und durch Kellerautomaten beschreiben und die Äquivalenz dieser Darstellungen beweisen, kennen den Satz von Chomsky und Schützenberger und seine anschauliche Bedeutung für die Struktur der Ableitungen in kontextfreien Sprachen, sind mit Normalformen, Abschlusseigenschaften, Entscheidbarkeits- und Komplexitätsaspekten insbesondere der regulären und kontextfreien Sprachen vertraut, können die Klasse der kontextsensitiven Sprachen durch kontextsensitive Grammatiken und Grammatiken vom Erweiterungstyp sowie durch linear beschränkte Automaten beschreiben und die Äquivalenz dieser Darstellungen beweisen. |
|
| Lerninhalte | Die Vorlesung gibt eine Einführung in die Theorie der formalen Sprachen und die dort verwendeten Begriffe und Methoden zur syntaktischen Sprachbeschreibung und -analyse unter besonderer Berücksichtigung algorithmischer Aspekte. Der Schwerpunkt der Vorlesung liegt auf den Sprachklassen der Chomsky-Hierarchie und deren Charakterisierung hinsichtlich der Beschreibbarkeit durch Grammatiken und der Erkennbarkeit durch Automaten. |
|
| Teilnahme- voraus- setzungen |
empfohlen ist: Einführung in die Theoretische Informatik (ITH) | |
| Vergabe der LP und Modulendnote | Bestehen der Modulprüfung | |
| Nützliche Literatur | ||