Modul "Grundlagen der Theoretischen Informatik (Informatik IV)"

Dozent: Prof. Dr. Jörg Rothe

Vorlesungsinhalte:

• Formale Sprachen und Automaten
  • Grundbegriffe
    • Wörter, Sprachen und Grammatiken
    • Die Chomsky-Hierarchie
  • Reguläre Sprachen
    • Endliche Automaten
    • Reguläre Ausdrücke
    • Gleichungssysteme
    • Das Pumping-Lemma
    • Satz von Myhill und Nerode und Minimalautomaten
    • Abschlusseigenschaften regulärer Sprachen
    • Charakterisierungen regulärer Sprachen
  • Kontextfreie Sprachen
    • Normalformen
    • Das Pumping-Lemma
    • Der Satz von Parikh
    • Abschlusseigenschaften kontextfreier Sprachen
    • Der Algorithmus von Cocke, Younger und Kasami
    • Kellerautomaten
  • Deterministisch kontextfreie Sprachen
    • Deterministische Kellerautomaten
    • LR(k)- und LL(k)-Grammatiken
    • Anwendung: Syntaxanalyse durch LL(k)-Parser
  • Kontextsensitive und Typ-0-Sprachen
    • Turingmaschinen
    • Linear beschränkte Automaten
    • Zusammenfassung
• Berechenbarkeit
  • Intuitiver Berechenbarkeitsbegriff und die These von Church
  • Turing-Berechenbarkeit
  • LOOP-, WHILE- und GOTO-Berechenbarkeit
    • LOOP-Berechenbarkeit
    • WHILE-Berechenbarkeit
    • GOTO-Berechenbarkeit
  • Primitiv rekursive und partiell rekursive Funktionen
    • Primitiv rekursive Funktionen
    • Die Ackermann-Funktion
    • Allgemein und partiell rekursive Funktionen
    • Der Hauptsatz der Berechenbarkeitstheorie
  • Entscheidbarkeit und Aufzählbarkeit
    • Einige grundlegende Sätze
    • Entscheidbarkeit
    • Rekursiv aufzählbare Mengen
  • Unentscheidbarkeit
    • Der Satz von Rice
    • Reduzierbarkeit
    • Das Postsche Korrespondenzproblem
    • Unentscheidbarkeit in der Chomsky-Hierarchie
    • Zusammenfassung

Literaturempfehlungen:

• Uwe Schöning: "Theoretische Informatik kurz gefasst", Spektrum Akademischer Verlag, 2. Auflage, 1995
• John E. Hopcroft, Rajeev Motwani und Jeffrey D. Ullman: "Einführung in die Automatentheorie, Formale Sprachen und Komplexitätstheorie", Pearson Studium, 2. Auflage, 2002
• Klaus W. Wagner: "Theoretische Informatik. Eine kompakte Einführung" Springer-Verlag, 2. Auflage, 2003
• Norbert Blum: "Theoretische Informatik. Eine anwendungsorientierte Einführung", Oldenbourg, 2. Auflage, 2001
• Alexander Asteroth und Christel Baier: "Theoretische Informatik. Eine Einführung in Berechenbarkeit, Komplexität und formale Sprachen mit 101 Beispielen", Pearson Studium, 2002