tatsächlicher Inhalt der Vorlesung Grundlagen der theoretischen Informatik

• Mittwoch, 18. 4. 2001
• Überblick: Sprachen, Automaten, Berechenbarkeit, Entscheidbarkeit
• Wörter und formale Sprachen
• Produkt von Wörtern und Sprachen, *-Operation
• reguläre Ausdrücke
• Mittwoch, 25. 4. 2001
• endliche Automaten
• Montag, 30. 4. 2001
• Simulation von nichtdeterministischen durch deterministische endliche Automaten
• Erkennen von regulären Ausdrücken durch nichtdeterministische endliche Automaten (ohne und mit epsilon-Übergängen)
• Vereinfachung von Automaten, unerreichbare Zustände
• Mittwoch, 2. 5. 2001
• Elimination von epsilon-Übergängen
• Darstellung von endlichen Automaten durch reguläre Ausdrücke
• Montag, 7. 5. 2001
• Isomorphie von Automaten
• Minimalautomaten: Konstruktion
• Mittwoch, 9. 5. 2001
• Minimalautomaten: Minimalität, Eindeutigkeit
• Isomorphietest für deterministische endliche Automaten

• Montag, 21. 5. 2001 (MS-Word, verstümmeltes HTML)
• Satz von Nerode, Nerode-Relation
• Sprachen die nicht regulär sind; Pumping-Lemma für reguläre Sprachen
• Abschlusseigenschaften regulärer Sprachen
• Testen von Eigenschaften regulärer Sprachen (Leerheit, Unendlichkeit, Gleichheit usw.)
• Mittwoch, 23. 5. 2001
• Syntaktische Analyse, Einführung in flex
• Konstruktion eines Scanners (grob)
• Montag, 28. 5. 2001
• Turingmaschinen
• Church'sche These
• rekursive (entscheidbare) und rekursiv aufzählbare Sprachen, Berechenbarkeit
• Mittwoch, 30. 5. 2001
• Unterprogrammtechnik für Turingmaschinen
• Diagonalisierung zur Konstruktion einer unentscheidbaren Sprache
• Mittwoch, 6. 6. 2001
• Universelle Turingmaschinen, die universelle Sprache
• Unentscheidbarkeit des Halteproblems
• Turingmaschinen mit mehreren Bändern
• Turingmaschinen, die eine Sprache aufzählen
• Montag, 11. 6. 2001: erste Klausur
• Stoff: Endliche Automaten und reguläre Sprachen, aber ausschließlich Pumping-Lemma und flex
• Mittwoch, 13. 6. 2001
• nichtdeterministische Turingmaschinen
• Zählermaschinen
• Grammatiken
• Die Chomsky-Hierarchie
• Tiefenstruktur von Sprachen
• Montag, 18. 6. 2001
• Äquivalenz von Typ-0-Grammatiken und Turingmaschinen
• Entscheidbarkeit von kontextsensitive Sprachen
• kontextfreie Grammatiken
• Rechts- und Linksableitungen, Syntaxbäume
• eindeutige und mehrdeutige Grammatiken
• Mittwoch, 20. 6. 2001
• Chomsky-Normalform für kontextfreie Grammatiken
• Das Pumping-Lemma für kontextfreie Sprachen
• Montag, 25. 6. 2001
• Beweis des Pumping-Lemmas
• Abschlusseigenschaften kontextfreier Sprachen
• Testen von Eigenschaften kontextfreier Grammatiken (Leerheit, Unendlichkeit, Gleichheit usw.)
• Entfernen überflüssiger Variablen
• Mittwoch, 27. 6. 2001
• Syntaxanalyse, Algorithmus von Coche-Younger-Kasami
• Backus-Naur-Form, Syntax von Programmiersprachen
• Kellerautomaten
• deterministische Zweiweg-Kellerautomaten
• Montag, 2. 7. 2001
• Simulation deterministischer Kellerautomaten in linearer Zeit
• nichtdeterministische Kellerautomaten
• Mittwoch, 4. 7. 2001
• nichtdeterministische Kellerautomaten und kontextfreie Sprachen
• deterministische kontextfreie Sprachen
• Montag, 9. 7. 2001
• deterministische kontextfreie Sprachen: Abgeschlossenheit gegenüber Komplement (nur skizziert)
• Typ-3-Grammatiken und reguläre Sprachen
• Beispiele kontextfreier Grammatiken in Sprachen, die in der Informatik eingesetzt werden: HTML (Netzseiten), XML, VRML (virtuelle Realität)
• Syntaxanalyse mit bison
• Mittwoch, 11. 7. 2001: zweite Klausur

• Turingmaschinen
• Auch ein primitives Modell kann mächtig sein.
• Es gibt Grenzen der algorithmischen Berechenbarkeit.
• Beziehungen zwischen verschiedenen Darstellungformen (endliche Automaten und reguläre Ausdrücke, deterministische und nichtdeterministische Turingmaschinen, Kellerautomaten und Grammatiken)
• Gleichwertig in der prinzipiellen Darstellungsfähigkeit
• Unterschiede in der Effizienz.