tatsächlicher Inhalt der Vorlesung Grundlagen der theoretischen Informatik

• Montag, 18. 4. 2005
• Überblick: Sprachen, Automaten, Berechenbarkeit, Entscheidbarkeit
• Wörter und formale Sprachen
• Produkt von Wörtern und Sprachen, *-Operation
• reguläre Ausdrücke
• Mittwoch, 20. 4. 2005
• endliche Automaten
• Montag, 25. 4. 2005
• Simulation von nichtdeterministischen durch deterministische endliche Automaten
• Erkennen von regulären Ausdrücken durch nichtdeterministische endliche Automaten (ohne und mit epsilon-Übergängen)
• Elimination von epsilon-Übergängen
• Mittwoch, 27. 4. 2005
• Übergang von endlichen Automaten zu regulären Ausdrücken (Satz von Kleene)
• Abschlusseigenschaften regulärer Sprachen
• die Nerode-Relation
• Montag, 2. 5. 2005
  
  • Vereinfachung von Automaten, unerreichbare Zustände
  • Minimalautomaten: Konstruktion, Minimalität, Eindeutigkeit
  • Satz von Nerode-Myhill
• Mittwoch, 4. 5. 2005
• Sprachen die nicht regulär sind; das Pumping-Lemma für reguläre Sprachen
• Turingmaschinen
• Church'sche These
• Mittwoch, 11. 5. 2005
• Programmierung von Turingmaschinen, Beispiel
• rekursive (entscheidbare) und rekursiv aufzählbare (semientscheidbare) Sprachen, Berechenbarkeit
• Mittwoch, 18. 5. 2005
• Anwendung regulärer Sprachen: Syntaktische Analyse, Einführung in das Programm (f)lex
• universelle Turingmaschinen
• Gödelnummerierung
• Montag, 23. 5. 2005
• Unentscheidbare Sprachen und Probleme: Diagonalsprache, Halteproblem, Postsches Korrespondenzproblem
• rekursiv aufzählbare Sprachen
• Mittwoch, 25. 5. 2005
• Reduzierbarkeit zwischen Problemen A und B (A<B)
• Simulation von Turingmaschinen mit Schleifenprogrammen
• Nichtberechenbarkeit
• Ausblick auf die Komplexitätstheorie
  
• primitiv-rekursive Funktionen und SCHLEIFE-berechenbare Funktionen (ohne Beweise)
  
• μ-rekursive Funktionen und WHILE-berechenbare Funktionen (ohne Beweise)
  
• Montag, 30. 5. 2005
  
• Grammatiken
• Die Chomsky-Hierarchie
• Tiefenstruktur von Sprachen
• Äquivalenz von Typ-0-Grammatiken und Turingmaschinen
• Mittwoch, 1. 6. 2005
  
• Entscheidbarkeit von kontextsensitive Sprachen
• kontextfreie Grammatiken
• Rechts- und Linksableitungen, Syntaxbäume
• eindeutige und mehrdeutige Grammatiken
• Montag, 13. 6. 2005
• Vermeidung mehrdeutiger Grammatiken; Beispiel: if-then-else-Klauseln
  
• Kontextfreie Grammatiken und Gleichungssysteme für Sprachen
• Elimination von epsilon-Regeln
• Chomsky-Normalform (CNF)
• Mittwoch, 15. 6. 2005
• Der Algorithmus von Cocke, Younger und Kasami für das Wortproblem in kontextfreien Sprachen
• Das Pumping-Lemma für kontextfreie Sprachen
• Montag, 20. 6. 2005
• Abschlusseigenschaften und Entscheidungsprobleme für kontextfreie Sprachen
  
• Typ-3-Grammatiken
• Mittwoch, 22. 6. 2005
• Kellerautomaten
• Montag, 27. 6. 2005
• Aquivalenz von Kellerautomaten und kontextfreien Sprachen
  
• Mittwoch, 29. 6. 2005
• Akzeptieren durch akzeptierende Zustände und durch leeren Keller
  
• deterministisch kontextfreie Sprachen
• Abgeschlossenheit gegenüber Komplement
• Montag, 4. 7. 2005
• deterministische Zweiweg-Kellerautomaten
• Simulation deterministischer Kellerautomaten in linearer Zeit
• Mittwoch, 6. 7. 2005
• Zusammenfassung und Überblick
  
• Montag, 11. 7. 2005: Abschlussklausur
• Mittwoch, 13. 7. 2005:
• Besprechung der Klausuraufgaben