Theoretische Informatik: Kontextfreie Sprachen und Kellerautomaten (#cofreeLangMOOC)

Kurslaufzeit:15.12.19 - 24.01.20
Sprache:Deutsch, Englisch
Dauer:6 Wochen
Niveau:Fortgeschritten

Was erwartet Dich in diesem Kurs?

Formale Sprachen und Automaten bilden die Grundlage, um Eingaben von NutzerInnen zu analysieren, angefangen bei Adressen in Web-Formularen bis hin zu komplexem Quelltext in Java. Diese dreiteilige Kursreihe liefert das theoretische Fundament. Er zeigt auch die Grenzen von Maschinenmodellen und von Berechenbarkeit im Allgemeinen. Dieser zweite Kurs dreht sich um kontextfreie Automaten und Kellerautomaten.

Was kannst du in diesem Kurs lernen?

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.

Wie ist der Kurs aufgebaut?

  1. Grammatiken
  2. Chomsky-Hierarchie
  3. Elimination von Epsilon-Produktionen
  4. Abschlusseigenschaften Kontextfreier Sprachen
  5. Das Pumping-Lemma für kontextfreie Sprachen
  6. Schnitt und Komplement
  7. Kellerautomaten
  8. Kellerautomaten und kontextfreie Sprachen

Wer führt diesen Kurs durch?

Prof. Dr. Andreas Schäfer

Prof. Dr. Andreas Schäfer

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.

Leistungsnachweis

In diesem Kurs kannst du Badges und ein Weiterbildungszertifikat erhalten.

Veranstalter

Technische Hochschule Lübeck

Kooperationspartner

Schleswig-Holstein - Ministerium für Soziales, Gesundheit, Jugend, Familie und Senioren

Lizenz

Sofern nicht gesondert angegeben, sind die Inhalte dieses Kurses lizenziert unter einer

Creative Commons - Attribution 4.0 International (CC BY 4.0)

Creative Commons - Attribution 4.0 International (CC BY 4.0)