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/ss2022_afs.php
- Lehrende(r): Jasmin Bille
- Lehrende(r): OUTDATED DO NOT USE
- Lehrende(r): Taisha Goetz
- Lehrende(r): Sebastian Gurke
- Lehrende(r): Thies Josten
- Lehrende(r): Sofie Teresa Kalthof
- Lehrende(r): Barbara König
- Lehrende(r): Liv Körting
- Lehrende(r): Shiyam Sivam
- Lehrende(r): Lara Stoltenow
- Lehrende(r): Fabian Urrigshardt