Inhalt
Automaten und Formale Sprachen: 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/ss2023_afs.php
- Lehrende(r): Larissa Barutta
- Lehrende(r): Jasmin Bille
- Lehrende(r): Taisha Goetz
- Lehrende(r): Sebastian Gurke
- Lehrende(r): Yaman Lahdo
- Lehrende(r): Michael Litvine
- Lehrende(r): Lara Stoltenow
- Lehrende(r): Fabian Urrigshardt
- Lehrende(r): Florian Wittbold