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.

Lernziele

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.

Kursaufbau

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

Ähnliche Lernangebote

DLC-Original
Kurs-Icon

Theoretische Informatik 1: Reguläre Sprachen und Endliche Automaten

location_city Digital Learning Campus

Zum Lernangebot navigate_next

location_on Online
signal_cellular_alt Fortgeschritten
language DE
Kurs-Icon

​Theory of Computing II: Contextfree Languages and PDAs

location_city Digital Learning Campus

Zum Lernangebot navigate_next

location_on Online
signal_cellular_alt Fortgeschritten
language EN
DLC-Original
Kurs-Icon

Theoretische Informatik 3: Berechenbarkeit und Komplexität

location_city Digital Learning Campus

Zum Lernangebot navigate_next

location_on Online
signal_cellular_alt Profi
language DE