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.
Weitere Materialien finden Sie im Stud.IP.