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

Mi, 16.04.2014
Eröffnungsveranstaltung. Kapitel 1: Einführung ins Thema. Organisatorisches.
Kapitel 2: Grundbegriffe zum Thema Wörter und Sprachen. Klassen, Abschlusseigenschaften, Klasse FIN, Abschlusseigenschaften von FIN
Beginn mit Kapitel 3: Endliche Automaten und reguläre Sprachen - heute: DFAs, Klasse REG, Pumping-Lemma
Material:
Skript "Diskrete Modellierung": Kapitel 7 (Endliche Automaten zur Modellierung von Abläufen)
Im Skript Kapitel 2 und Kapitel 3.1 (bis einschließlich 3.1.1.)
Videoaufzeichnung der Vorlesung:
Übungsaufgaben:
Übungsblatt 1 wurde ausgeteilt. (In Aufgabe 3 war das echte Teilmengenzeichen zuerst fälschlicherweise ein echtes Obermengenzeichen.)
Mi, 23.04.2014
weiter mit Kapitel 3: Endliche Automaten und reguläre Sprachen - heute: Komplement- und Produktautomat, Abschlusseigenschaften, Nerode-Relation
Material:
Im Skript Kapitel 2 und Kapitel 3.1 (bis einschließlich 3.1.3., aber noch nicht den Beweis des Myhill-Nerode-Satzes)
Videoaufzeichnung der Vorlesung:
Übungsaufgaben:
Übungsblatt 2 wurde ausgeteilt.
Mi, 30.04.2014
weiter mit Kapitel 3: Endliche Automaten und reguläre Sprachen - heute: Satz von Myhill-Nerode fertig bewiesen, Minimierung von DFAs
Material:
Im Skript Kapitel 3.1 (bis einschließlich 3.1.5). Schwerpunkt auf dem Minimierungs-Algorithmus.
Videoaufzeichnung der Vorlesung:
Weitere Lektüre
Kapitel 3.10 in [S-Sec],
Diese Veröffentlichung, in der mehrere Algorithmen zur Minimierung von DFAs verglichen werden.
Übungsaufgaben:
Übungsblatt 3 wurde ausgeteilt.
Mi, 07.05.2014
weiter mit Kapitel 3: Endliche Automaten und reguläre Sprachen - heute: NFAs, NFAs mit nichtdeterministischem Startzustand, NFAs mit ε-Übergängen, Brzozowskis Algorithmus, Reversal-Konstruktion.
Material:
Im Skript Kapitel 3.2 (bis einschließlich 3.2.3).
Videoaufzeichnung der Vorlesung:
Übungsaufgaben:
Übungsblatt 4 wurde ausgeteilt.
Mi, 14.05.2014
weiter mit Kapitel 3: Endliche Automaten und reguläre Sprachen - heute: Abschluss der Klasse REG unter Vereinigung, Konkatenation und Kleene-Stern anhand von ε-NFAs, reguläre Ausdrücke, erweiterte NFAs, sowie Substitution, Homomorphismus und inverser Homomorphismus.
Material:
Im Skript von Kapitel 3.2.4 bis einschließlich 3.3.2). Beachten Sie besonders den Algorithmus ENFA2RegEx und die Beispiele in Kapitel 3.3.2.
Videoaufzeichnung der Vorlesung:
Weitere Lektüre
In der Vorlesung wurde kurz über die Programmbibliotheken für reguläre Ausdrücke gesprochen, die stark automatentheoretisch geprägt sind:
  • RE2: Die Webseite des Projekts finden Sie dort. Besonders relevant ist dieser Text zu den theoretischen Hintergründen.
  • redgrep: Auf der Webseite habe ich nicht viel dazu gefunden, aber es gibt ein Video (YouTube), das ein wenig den Hintergrund erläutert. Die regular expression derivatives, von denen dort die Rede ist, sind ähnlich zu den Ableitungen von regulären Sprachen definiert, die wir bereits aus der Vorlesung kennen.
Übungsaufgaben:
Übungsblatt 5 wurde ausgeteilt.
Mi, 21.05.2014
weiter mit Kapitel 3: Endliche Automaten und reguläre Sprachen - heute: Entscheidungsprobleme, reguläre Grammatiken. Einstieg in Kapitel 4: Kontextfreie Sprachen - heute: Kontextfreie Grammatiken, Abschlusseigenschaften, Ableitungsbäume.
Material:
Im Skript von Kapitel 3.4 bis einschließlich 4.1.
Videoaufzeichnung der Vorlesung
Weitere Lektüre
In der Vorlesung wurde wieder kurz über die Programmbibliotheken für reguläre Ausdrücke gesprochen, die stark automatentheoretisch geprägt sind. Damit Sie nicht scrollen müssen hier noch einmal die Links:
  • RE2: Die Webseite des Projekts finden Sie dort. Besonders relevant ist dieser Text zu den theoretischen Hintergründen.
  • redgrep: Auf der Webseite habe ich nicht viel dazu gefunden, aber es gibt ein Video (YouTube), das ein wenig den Hintergrund erläutert. Die regular expression derivatives, von denen dort die Rede ist, sind ähnlich zu den Ableitungen von regulären Sprachen definiert, die wir bereits aus der Vorlesung kennen.
Übungsaufgaben:
Übungsblatt 6 wurde ausgeteilt.
Mi, 28.05.2014
weiter mit Kapitel 4: Kontextfreie Sprachen - heute: Das Pumping-Lemma für Kontextfreie Sprachen, (Nicht-)Abschlusseigenschaften, Chomsky-Normalform.
Material:
Im Skript Kapitel 4.1.1 und 4.1.2.
Videoaufzeichnung der Vorlesung
Übungsaufgaben:
Übungsblatt 7 wurde ausgeteilt.
Mi, 04.06.2014
weiter mit Kapitel 4: Kontextfreie Sprachen - heute: Der CYK-Algorithmus und Mehrdeutigkeit.
Material:
Im Skript Kapitel 4.1.3 und 4.1.4.
Videoaufzeichnung der Vorlesung
Übungsaufgaben:
Übungsblatt 8 wurde ausgeteilt. Leider hatten sich ein paar Fehler eingeschlichen; beachten Sie bitte die Hinweise auf der Seite zur Vorlesung (unter Aktuelles).
Mi, 11.06.2014
weiter mit Kapitel 4: Kontextfreie Sprachen - heute: Kellerautomaten (und der Abschluss der Klasse der kontextfreien Sprachen unter inversen Homomorphismen).
Material:
Im Skript Kapitel 4.2 bis einschließlich 4.2.1.
Videoaufzeichnung der Vorlesung
Übungsaufgaben:
Übungsblatt 9 wurde ausgeteilt.
Mi, 18.06.2014
weiter mit Kapitel 4: Kontextfreie Sprachen - heute: deterministische Kellerautomaten (und deterministisch kontextfreie Sprachen), Entscheidungsprobleme für kontextfreie Sprachen (und das Postsche Korrespondenz Problem).
Material:
Im Skript Kapitel 4.2.2 und 4.3
Videoaufzeichnung der Vorlesung
Bonus-Material
Dort können Sie ein Programm zum Lösen von (manchen) PCP-Instanzen herunterladen.
Übungsaufgaben:
Übungsblatt 10 wurde ausgeteilt.
Mi, 25.06.2014
Wiederholung der Tripelkonstruktion. Einstieg in Kapitel 5: Jenseits der kontextfreien Sprachen. Kontextsensitive Sprachen (kontextsensitive und monotone Grammatiken, LBAs) und die Chomsky-Hierarchie.
Material:
Im Skript Kapitel 4.2.1, 5.1 und 5.2
Videoaufzeichnung der Vorlesung
  • Die E-Lecture V11 [HTML5 | Flash | Quicktime | mobile | audio]
    Aus technischen Gründen wurden die Folien bei dieser Vorlesung nicht mit aufgezeichnet. Wir bedauern dies zutiefst, weisen aber gleichzeitig auch darauf hin, dass wir auf die technische Seite der Aufzeichnungen keinen Einfluss haben.
Übungsaufgaben:
Übungsblatt 11 wurde ausgeteilt.
Mi, 02.07.2014
Weiter Kapitel 5: Jenseits der kontextfreien Sprachen. Patternsprachen und erweiterte reguläre Ausdrücke.
Material:
Im Skript Kapitel 5.3
Videoaufzeichnung der Vorlesung
Weitere Lektüre
In der Vorlesung wurde kurz erwähnt, dass mit erweiterten regulären Ausdrücken Sudoku gelöst werden kann. Eine Skizze der (nicht wirklich praktischen) Herangehensweise findet sich dort.
Übungsaufgaben:
Übungsblatt 12 wurde ausgeteilt.
Mi, 09.07.2014
Einstieg Kapitel 6: Anwendungen. Heute: XML, deterministische reguläre Ausdrücke und Glushkov-Automaten.
Material:
Im Skript Kapitel 6.1
Videoaufzeichnung der Vorlesung
Übungsaufgaben:
Heute wurde kein Übungsblatt ausgeteilt. Zum Abschluss des Semesters wird es noch ein unbepunktetes Bonusblatt geben (ohne Abgabe, Besprechung oder Korrektur; aber mit Lösungshinweisen).
Mi, 16.07.2014
Weiter mit Kapitel 6: Anwendungen. Heute: Pattern-Matching.
Material:
Im Skript Kapitel 6.2
Videoaufzeichnung der Vorlesung
Übungsaufgaben:
Übungsblatt 13 wurde ausgeteilt. Dieses Blatt wird nicht abgegeben und auch nicht korrigiert. Lösungshinweise zu diesen Aufgaben sind hier verfügbar.