Die Theorie der formalen Sprachen bildet die Grundlage für viele andere Gebiete der Informatik, beispielsweise für Informationsverarbeitung, Compilerbau, Verifikation, Modellierung. Im Rahmen dieser Veranstaltung werden die Grundlagen der formalen Sprachen vermittelt und Fertigkeiten im Umgang mit Automaten und Grammatiken eingeübt. Außerdem soll vermittelt werden, in welchen Bereichen diese Theorie zur Anwendung kommt. Im Einzelnen wird dabei behandelt:
- Grammatiken, Chomsky-Hierarchie
- Wortproblem, Syntaxbäume
- Reguläre Sprachen (Endliche Automaten, Reguläre Ausdrücke, Pumping-Lemma, Äquivalenzrelationen und Minimalautomaten, Abschlusseigenschaften, Endscheidbarkeit, Anwendung: Verifikation eines Protokolls zum wechselseitigen Ausschluss)
- Kontextfreie Sprachen (Normalformen, Pumping-Lemma, CYK-Algorithmus, Kellerautomaten, deterministisch kontextfreie Sprachen Abschlusseigenschaften, Entscheidbarkeit)
- Kontextsensitive und Typ-0-Sprachen
Weitere Informationen zu dieser Veranstaltung finden Sie unter https://www.uni-due.de/theoinf/teaching/ss2025_afs.php
- verantwortliche Lehrperson: Lara Stoltenow
- begleitende Lehrperson: Mara Arnold
- begleitende Lehrperson: Larissa Barutta
- begleitende Lehrperson: Cora Jostock
- begleitende Lehrperson: Barbara König
- begleitende Lehrperson: Florian König
- begleitende Lehrperson: Chuhua Lin