Formale Sprachen

Moduldetails

Dozent: Dr. Arne Meier

Frequenz: zweijährlich (ungerade) im Sommersemester

Veranstaltungsart: Vorlesung und Übung (2V + 2Ü, 5 CP)

Prüfung: mündl. Prüfung
Vorlesungsinhalte
Das Modul vermittelt vertiefte Kenntnisse über formale Sprachen. Die Studierenden analysieren Phänomene aus der Theorie der formalen Sprachen über die Inhalte der Grundvorlesungen hinaus. Sie konstruieren verschiedenartige Automaten und Grammatikmodelle für reguläre und kontextfreie Sprachen. Sie beurteilen die gängigen Transformationen und sonstigen Verfahren für diese Modelle. Sie beurteilen die Möglichkeiten zur Anwendungen für die Syntaxanalyse. Sie verstehen die relevanten Entscheidbarkeitsresultate und sind in der Lage, diese auf verwandte Probleme zu übertragen.

Inhalt:

Die regulären und kontextfreien Sprachen spielen eine äußerst wichtige Rolle im Compilerbau und weiteren Disziplinen der Informatik. In der Vorlesung werden schwerpunktmäßig diese beiden Sprachklassen betrachtet und ihre Eigenschaften untersucht.

Gliederung:
Endliche Automaten
Satz von Myhill-Nerode
Minimalautomaten
Automaten und Halbgruppen
Chomsky-Normalform und CYK-Algorithmus
Greibach-Normalform und Kellerautomaten
Deterministisch-kontextfreie Sprachen
Entscheidbarkeitsfragen
Kontextsensitive Sprachen und Typ-0-Sprachen.
Informationen zur Prüfung

Die Abschlussprüfung des Moduls ist eine mündliche Prüfung.

Termin

Die Prüfungstermine vergeben wir über eine institutsinterne Website (siehe Link unten). Achtung: Dies ersetzt nicht die Anmeldung der Prüfung im QIS.

Anmeldung

Je nach Prüfungsordnung ist eine Anmeldung im QIS erforderlich (siehe Link unten).

Studienleistung

Falls Ihre Prüfungsordnung eine Studienleistung für dieses Modul vorsieht, kontaktieren Sie bitte den Dozenten.

Materialien

Zu dieser Veranstaltung gibt es Vorlesungsaufzeichnungen.

Zu den Aufzeichnungen

Weitere Materialien finden Sie im Stud.IP.

Zum Stud.IP

Inhalt:

Gliederung:

Materialien