Hier finden Sie (nach den Vorlesungen) Informationen zum Inhalt der einzelnen Vorlesungsstunden sowie gelegentlich ergänzende Bemerkungen.

Do, 12.04.2012
Eröffnungsveranstaltung. Kapitel 1: Einführung ins Thema. Organisatorisches. Einige Grundbegriffe zum Thema Worte und Sprachen.
Beginn mit Kapitel 2: Endliche Automaten und reguläre Sprachen - heute: DFAs, NFAs und Mealy Automaten.
Material:
Skript "Diskrete Modellierung": Kapitel 7 (Endliche Automaten zur Modellierung von Abläufen)
Prof. Schnitgers Skript "Formale Sprachen und Berechenbarkeit" (SoSe 2011): Kapitel 1 (Einführung) und Kapitel 2 (Endliche Automaten)
Vortragsfolien
Videoaufzeichnung der Vorlesung: Die E-Lectures zu den Themen
  • Einführung ins Thema
  • NFAs, DFAs und Mealy Automaten
Weitere Lektüre:
Kapitel 1 sowie Kapitel 2.1-2.3 und 2.7-2.8 in [HU], Kapitel 1.2.1-1.2.3 in [S-Theo], Kapitel 4.1 und 4.4 in [W-Theo], Kapitel 4 in [W-Komp]
Übungsaufgaben:
Übungsblatt 1 wurde ausgeteilt. Zusätzlich dazu kann ein Blatt mit Präsenzaufgaben, deren Lösung in der ersten Übungsstunde besprochen wird, hier heruntergeladen werden.
Do, 19.04.2012
Weiter mit Kapitel 2: Endliche Automaten und reguläre Sprachen - heute: Minimierung von DFAs; insbesondere: der Äquivalenzklassenautomat
Material:
Prof. Schnitgers Skript "Formale Sprachen und Berechenbarkeit" (SoSe 2011): Kapitel 2 (Endliche Automaten)
Vortragsfolien und ein Beispiel zur Konstruktion des Äquivalenzklassenautomaten (Tafelanschrieb)
Videoaufzeichnung der Vorlesung: Die E-Lecture zum Thema
  • DFA-Minimierung
Weitere Lektüre:
Kapitel 3.4 in [HU], Kapitel 1.2.5 in [S-Theo], Kapitel 4.2 in [W-Theo], Kapitel 4 in [W-Komp]
Übungsaufgaben:
Übungsblatt 2 wurde ausgeteilt.
Anmerkung: Aufgabe 2 wird von Blatt 2 gestrichen, da die darin verwendeten Begriffe in der Vorlesung vom 19.04.2012 noch nicht behandelt wurden. Die Punkte für die verbleibenden Aufgaben werden wie folgt verteilt: Aufgabe 1: 34 Punkte, Aufgabe 3: 26 Punkte, Aufgabe 4: 20 + 20 = 40 Punkte.
Do, 26.04.2012
Weiter mit Kapitel 2: Endliche Automaten und reguläre Sprachen - heute: Der Satz von Myhill und Nerode, das Pumping Lemma
Material:
Prof. Schnitgers Skript "Formale Sprachen und Berechenbarkeit" (SoSe 2011): Kapitel 2 (Endliche Automaten)
Vortragsfolien
Videoaufzeichnung der Vorlesung: Die E-Lecture zum Thema
  • Der Satz von Myhill-Nerode und das Pumping Lemma
Weitere Lektüre:
Kapitel 3.4 und 3.1 in [HU], Kapitel 1.2.5 und 1.2.4 in [S-Theo], Kapitel 4.2 und 4.3 in [W-Theo], Kapitel 4 in [W-Komp]
Übungsaufgaben:
Übungsblatt 3 wurde ausgeteilt.
Do, 03.05.2012
Weiter mit Kapitel 2: Endliche Automaten und reguläre Sprachen - heute: Beispiele für die Anwendung (und das Scheitern) des Pumping Lemmas, untere Schranken für die Größe von NFAs, NFAs mit epsilon-Übergängen, Abschlusseigenschaften der Klasse aller regulären Sprachen
Material:
Prof. Schnitgers Skript "Formale Sprachen und Berechenbarkeit" (SoSe 2011): Kapitel 2 (Endliche Automaten)
Vortragsfolien
Videoaufzeichnung der Vorlesung: Die E-Lecture zum Thema
  • Untere Schranken für die Größe von NFAs, NFAs mit epsilon-Übergängen, Abschlusseigenschaften der Klasse aller regulären Sprachen
Weitere Lektüre:
Kapitel 3.1, 2.4 und 3.2 in [HU], Kapitel 1.2.4 und 1.2.6 in [S-Theo], Kapitel 4.2 und 4.3 in [W-Theo], Kapitel 4 in [W-Komp].
Die "Fooling Set Methode" zum Nachweis unterer Schranken an die Größe von NFAs wird in der folgenden Arbeit beschrieben: I. Glaister, J. Shallit, A lower bound technique for the size of nondeterministic finite automata, Information Processing Letters 59, pages 75-77, 1996.
Übungsaufgaben:
Übungsblatt 4 wurde ausgeteilt.
Do, 10.05.2012
Weiter mit Kapitel 2: Endliche Automaten und reguläre Sprachen - heute: Homomorphismen, Beispiele für die Anwendung der Abschlusseigenschaften der Klasse aller regulären Sprachen, Entscheidungsprobleme, reguläre Ausdrücke
Material:
Prof. Schnitgers Skript "Formale Sprachen und Berechenbarkeit" (SoSe 2011): Kapitel 2 (Endliche Automaten)
Vortragsfolien
Videoaufzeichnung der Vorlesung: Die E-Lecture zum Thema
  • Homomorphismen, Anwendung der Abschlusseigenschaften der Klasse aller regulären Sprachen, Entscheidungsprobleme, reguläre Ausdrücke
Weitere Lektüre:
Kapitel 3.2, 3.3 und 2.5 in [HU], Kapitel 1.2.6, 1.2.7 und 1.2.3 in [S-Theo], Kapitel 4.6 und 5.3 in [W-Theo], Kapitel 4 in [W-Komp].
Übungsaufgaben:
Übungsblatt 5 wurde ausgeteilt.
Do, 24.05.2012
Abschluss von Kapitel 2: Endliche Automaten und reguläre Sprachen - heute: Der Satz von Kleene, reguläre Ausdrücke für Komplement und Durchschnitt, reguläre Grammatiken, Zusammenfassung der in Kapitel 2 behandelten Themen
Beginn mit Kapitel 3: Kontextfreie Sprachen - heute: Beispiele für kontextfreie Grammatiken
Material:
Prof. Schnitgers Skript "Formale Sprachen und Berechenbarkeit" (SoSe 2011): Kapitel 2 (Endliche Automaten) und Kapitel 3 (Kontextfreie Sprachen)
Vortragsfolien und Beweis, dass eine in der Vorlesung entwickelte KFG die Sprache aller Worte mit gleich vielen Nullen wie Einsen erzeugt (Tafelanschrieb)
Videoaufzeichnung der Vorlesung: Die E-Lectures zu den Themen
  • Der Satz von Kleene, reguläre Ausdrücke für Durchschnitt und Komplement, reguläre Grammatiken
  • Beispiele für kontextfreie Grammatiken
Weitere Lektüre:
Kapitel 2.5, 9.1, 4.1 und 4.2 in [HU], Kapitel 1.2.3 und 1.3 in [S-Theo], Kapitel 5.3 und 6.1 in [W-Theo], Kapitel 4 und 6 in [W-Komp].
Die unteren Schranken für die Größe von regulären Ausdrücken für Komplement und Durchschnitt finden sich in in der folgenden Arbeit: W. Gelade, F. Neven, Succinctness of the Complement and Intersection of Regular Expressions. ACM Transactions on Computational Logic, Volume 13, Issue 1, Article No. 4, 2012.
Übungsaufgaben:
Übungsblatt 6 wurde ausgeteilt.
Do, 31.05.2012
Weiter mit Kapitel 3: Kontextfreie Sprachen - heute: kontextfreie Grammatiken für Programmiersprachen; Ableitungsbäume und eindeutige Grammatiken; Pumping Lemma und Ogden's Lemma; Chomsky Normalform
Material:
Prof. Schnitgers Skript "Formale Sprachen und Berechenbarkeit" (SoSe 2011): Kapitel 3 (Kontextfreie Sprachen)
Vortragsfolien
Videoaufzeichnung der Vorlesung: Die E-Lecture zum Thema
  • Kontextfreie Grammatiken für Programmiersprachen; Ableitungsbäume und eindeutige Grammatiken; Pumping Lemma und Ogden's Lemma
Weitere Lektüre:
Kapitel 4.3, 4.5 und 6.1 in [HU], Kapitel 1.3.1 und 1.3.2 in [S-Theo], Kapitel 6.1, 6.2, 6.4 in [W-Theo], Kapitel 6 in [W-Komp].
Übungsaufgaben:
Übungsblatt 7 wurde ausgeteilt.
Do, 14.06.2012
Weiter mit Kapitel 3: Kontextfreie Sprachen - heute: Beweis von Ogden's Lemma; Abschlusseigenschaften der Klasse aller kontextfreien Sprachen; Kellerautomaten (PDAs)
Material:
Prof. Schnitgers Skript "Formale Sprachen und Berechenbarkeit" (SoSe 2011): Kapitel 3 (Kontextfreie Sprachen)
Vortragsfolien
Videoaufzeichnung der Vorlesung: Die E-Lecture zum Thema
  • Beweis von Odgen's Lemma; Abschlusseigenschaften der Klasse aller kontextfreien Sprachen; Kellerautomaten
Weitere Lektüre:
Kapitel 6.1, 6.2, 5.1, 5.2 in [HU], Kapitel 1.3.2, 1.3.3, 1.3.5 in [S-Theo], Kapitel 6.4, 6.5, 7.2 in [W-Theo], Kapitel 6 in [W-Komp].
Übungsaufgaben:
Übungsblatt 8 wurde ausgeteilt.
Do, 21.06.2012
Abschluss von Kapitel 3: Kontextfreie Sprachen - heute: Äquivalenz zwischen Kellerautomaten und kontextfreien Sprachen (u.a.: die Tripelkonstruktion); deterministisch kontextfreie Sprachen; das Wortproblem für kontextfreie Sprachen (der CYK-Algorithmus)
Material:
Prof. Schnitgers Skript "Formale Sprachen und Berechenbarkeit" (SoSe 2011): Kapitel 3 (Kontextfreie Sprachen)
Vortragsfolien und ein Beispiellauf des CYK-Algorithmus (Tafelanschrieb)
Videoaufzeichnung der Vorlesung: Die E-Lecture zum Thema
  • Äquivalenz zwischen Kellerautomaten und kontextfreien Sprachen; deterministisch kontextfreie Sprachen; der CYK-Algorithmus
Weitere Lektüre:
Kapitel 5.3, 10.1-10.3, 6.3 in [HU], Kapitel 1.3.5, 1.3.6, 1.3.4 in [S-Theo], Kapitel 6 und 7 in [W-Theo], Kapitel 6 in [W-Komp].
Übungsaufgaben:
Übungsblatt 9 wurde ausgeteilt.
Do, 28.06.2012
Beginn mit Kapitel 4: Berechenbarkeit - heute: Das Halteproblem, Entscheidbarkeit, Semi-Entscheidbarkeit, Rekursive Aufzählbarkeit, Berechenbarkeit, der Satz von Rice, (Einleitung zum Thema) Turingmaschinen
Material:
Prof. Schnitgers Skript "Formale Sprachen und Berechenbarkeit" (SoSe 2011): Kapitel 5 (Berechenbarkeit)
Turingmaschinen in Aktion (auf YouTube): A Turing Machine In The Classic Style und The LEGO Turing Machine
Vortragsfolien
Videoaufzeichnung der Vorlesung: Die E-Lecture zum Thema
  • Halteproblem, (Semi-)Entscheidbarkeit, Rekursive Aufzählbarkeit, Berechenbarkeit, Satz von Rice, Turingmaschinen (Aufzeichnung vom 02.07.2012)
Weitere Lektüre:
Kapitel 7 und 8 in [HU], Kapitel 2 in [S-Theo], Kapitel in [W-Theo], Kapitel 2 in [W-Komp].
Übungsaufgaben:
Übungsblatt 10 wurde ausgeteilt.
Do, 05.07.2012
Weiter mit Kapitel 4: Berechenbarkeit - heute: Turingmaschinen, die Church-Turing-These, Mehrband-Turingmaschinen, Gödelnummern, universelle Turingmaschine, Reduktionen, Unentscheidbarkeit der Diagonalsprache D und der universellen Sprache U
Material:
Prof. Schnitgers Skript "Formale Sprachen und Berechenbarkeit" (SoSe 2011): Kapitel 5 (Berechenbarkeit)
Turingmaschinen in Aktion (auf YouTube): A Turing Machine In The Classic Style und The LEGO Turing Machine
Vortragsfolien
Videoaufzeichnung der Vorlesung: Die E-Lecture zum Thema
  • (Mehrband-)Turingmaschinen, Church-Turing-These, Gödelnummern, universelle Turingmaschine, Reduktionen, Unentscheidbarkeit der Diagonalsprache und der universellen Sprache (Aufzeichnung vom 05.07.2012)
Weitere Lektüre:
Kapitel 7 und 8 in [HU], Kapitel 2 in [S-Theo], Kapitel in [W-Theo], Kapitel 2 in [W-Komp].
Übungsaufgaben:
Übungsblatt 11 wurde ausgeteilt.
Do, 12.07.2012
Abschluss von Kapitel 4: Berechenbarkeit - heute: Unentscheidbarkeit des Halteproblems H und des speziellen Halteproblems Hε, das Postsche Korrespondenzproblem PKP, unentscheidbare Grammatik-Probleme (u.a. "leerer Schnitt", "Subsumption", "Äquivalenz", "Mehrdeutigkeit" und "Regularität" für KFGs, sowie "leerer Schnitt" und "Äquivalenz" für DPDAs).
Kapitel 5: Die Chomsky Hierarchie - heute: allgemeine Grammatiken (Typ 0), kontextsensitive Grammatiken (Typ 1), kontextfreie Grammatiken (Typ 2), reguläre Grammatiken (Typ 3), Charakterisierung der Typ 0-Sprachen als die semi-entscheidbaren Sprachen, Charakterisierung der kontextsensitiven Sprachen als die durch linear beschränkte Automaten (nichtdeterministische linear Platzbeschränkte Turingmaschinen) erkennbaren Sprachen.
Material:
Prof. Schnitgers Skript "Formale Sprachen und Berechenbarkeit" (SoSe 2011): Kapitel 5 (Berechenbarkeit) und Kapitel 6 (Komplexitätsklassen und die Chomsky Hierarchie)
Vortragsfolien
Videoaufzeichnung der Vorlesung: Die E-Lectures zu den Themen
  • Unentscheidbarkeit des Halteproblems und des speziellen Halteproblems, Unentscheidbarkeit des Postschen Korrespondenzproblems, unentscheidbare Grammatik-Probleme (Aufzeichnung vom 12.07.2012)
  • Die Chomsky Hierarchie (Aufzeichnung vom 12.07.2012)
Weitere Lektüre:
Kapitel 8 und 9 in [HU], Kapitel 2.6, 2.7, 2.8 und 1.1.2 und 1.3.7 und 1.4 und 1.5 in [S-Theo], Kapitel 2.6, 2.7, 2.8 und 6.6 und 5 in [W-Theo], Kapitel 2, 6 und 5 in [W-Komp].
Do, 19.07.2012
Hilfestellungen zur Klausurvorbereitung. Insbes.: Details zum Ablauf der Klausur, Zusammenfassung der wichtigsten in Vorlesung und Übung behandelten Themen, Durcharbeiten von Teilen der zweiten Klausur aus dem Sommersemester 2010.
Material:
Prof. Schnitgers Skript "Formale Sprachen und Berechenbarkeit" (SoSe 2011)
"offiziell erlaubter Spickzettel", der bei der Klausur ausgeteilt wird
Klausuren aus früheren Semestern: die Klausuren aus dem SoSe 2002, die erste Klausur aus dem SoSe 2010, die zweite Klausur aus dem SoSe 2010.
Videoaufzeichnung der Vorlesung: Die E-Lecture zum Thema
  • Zusammenfassung der wichtigsten in Vorlesung und Übung behandelten Themen sowie Hilfestellungen zur Klausurvorbereitung (Aufzeichnung vom 19.07.2012)
Weitere Lektüre:
Das komplette Buch [W-Komp], Kapitel 9 in [W-Theo], Kapitel 1.5 in [S-Theo].