Theoretische Informatik: Kontextfreie Sprachen und Kellerautomaten
Author: | Andreas Schäfer | ||
Offering Institution: | Technische Hochschule Lübeck | ||
Course Language: | German | ||
Field of Knowledge: | Preparation Courses | Free of Charge | |
Average Workload: | 50 Hours | Free of Charge | Enrol |
What can you learn in this course?
Mit der Hilfe dieses Kurses sollen diese Lernziele ermöglicht werden:
- Du kannst die formale Notation einer Grammatik lesen und schreiben und einfache Grammatiken innerhalb der Chomsky-Hierarchie zuordnen.
- Du kannst Epsilon-Produktionen aus Grammatiken entfernen.
- Du kannst benennen, unter welchen Operationen kontextfreie Grammatiken abgeschlossen sind.
- Du kannst beweisen, dass eine Sprache nicht kontextfrei ist.
- Du kannst die Idee und Funktionsweise von Kellerautomaten beschreiben.
- Du kannst kontextfreie Grammatiken in Kellerautomaten überführen.
Outline
- Grammatiken
- Chomsky-Hierarchie
- Elimination von Epsilon-Produktionen
- Abschlusseigenschaften Kontextfreier Sprachen
- Das Pumping-Lemma für kontextfreie Sprachen
- Schnitt und Komplement
- Kellerautomaten
- Kellerautomaten und kontextfreie Sprachen
Further authors

Prof. Dr. Andreas Schäfer
Andreas Schäfer promovierte 2007 an der Carl von Ossietzky University in Oldenburg.
Es arbeitete dann für fünf Jahre beim Europäischen Patentbüro. Seit 2012 ist er Professor der Informatik an der Technischen Hochschule in Lübeck. Seine Interessenschwerpunkte umfassen Automatentheorie, Logik und formale Methoden.