Nach dem Abschluss dieses Moduls kennen die Studierenden die Typen von Grammatiken in der Chomsky-Hierarchie, die von diesen Grammatiken erzeugten Sprachen und die diese Sprachen erkennenden Automaten und können diese sicher anwenden. Außerdem haben sie Einsicht in die Beziehungen zwischen den Konzepten Sprache/Problem, Wort/Programmeingabe und - ausgabe, Automatenregeln/Programm.

  • Allgemeines 
  • Chomsky-Hierarchie 
  • Wortproblem 
  • Syntaxbäume 
  • Backus-Naur-Form Reguläre Sprachen 
  • Endliche Automaten 
  • Nichtdeterministische Automaten 
  • Reguläre Ausdrücke 
  • Das Pumping Lemma 
  • Äquivalenzrelationen und Minimalautomaten 
  • Abschlusseigenschaften
  • Entscheidbarkeit Kontextfreie Sprachen 
  • Normalformen 
  • Das Pumping Lemma 
  • Abschlusseigenschaften
  • Der CYK-Algorithmus 
  • Kellerautomaten 
  • Deterministisch kontextfreie Sprachen 
  • Entscheidbarkeit bei kontextfreien Sprachen Kontextsensitive und Typ-0-Sprachen 
  • Turing-Maschinen