Theoretische Informatik 2

Vorlesung im SoSe 2014

Gehalten von Dr. Dominik D. Freydenberger
Betreuung der Übungen durch Dipl.-Inf. Joachim Bremer

Aktuelles

Im Logbuch finden Sie nach den Vorlesungen Informationen zum Inhalt der einzelnen Vorlesungsstunden und gelegentlich ergänzende Bemerkungen.

Da die Vorlesung abgeschlossen ist, wurden die (nicht mehr wirklich) aktuellen Hinweise ausgeblendet. Sie können allerdings hier wieder eingeblendet werden.

In folgender PDF-Datei finden Sie die Ergebnisse der Klausur vom 29.07.14. Die Klausureinsicht findet am 12.8.14 von 12:00 Uhr bis 13:00 Uhr im Raum 117, Robert-Mayer-Straße 11-15 statt.
Die Lösungshinweise für Blatt 13 sind nun hier verfügbar.
Leider war Aufgabe 1d auf Übungsblatt 12 wahrscheinlich mit den Ihnen zur Verfügung stehenden Mitteln nicht lösbar. Deswegen wurde die Maximalpunktezahl von Übungsblatt 12 um 9 Punkte reduziert. Dies hatte leichte Veränderungen bei den Bonuspunkten zur Folge. Die erreichbare Maximalpunktezahl aller 12 Übungsblätter zusammen ist somit 1166.
Die Bonuspunkte dieses Semesters können in folgender PDF-Datei eingesehen werden. Nur wer vorgerechnet hat, erhält Bonuspunkte! Bitte prüfen Sie, ob Ihre Bonuspunkte korrekt in der Liste eingetragen sind. Einsprüche gegen den in der Liste eingetragenen Punktestand müssen bis spätestens Donnerstag, den 24.07.2014, 12:00 Uhr bei Dominik Freydenberger erfolgen.
Achtung: Das Skript wurde in Bezug auf die Tripelkonstruktion stark überarbeitet. Besonders sind diese Änderungen zu erwähnen:
- Zwischen dem Beweis von Lemma 4.70 und Hinweis 4.71 finden Sie nun eine ausführliche Erläuterung mit (hoffentlich hilfreichen) Tips zum Durchführen der Tripelkonstruktion. Sie erkenn diese Erläuterung an den roten Pfeilen.
- Das frühere Beispiel 4.72 wurde gestrichen, da die Methode sich als unnötig verwirrend erwiesen hat. Mit der anderen (empfohlenen) Methode wäre diese Konstruktion dem früheren Beispiel 4.73 (jetzt 4.72) zu ähnlich gewesen. Deswegen wurde stattdessen ein neues Beispiel aufgenommen, das besonders auf Optimierung durch Erreichbarkeit in PDAs mit größeren Zyklen eingeht.
- Hinweis 4.71 wurde überarbeitet und besser an die Erläuterungen davor angepasst.
Außerdem fehlte auf Blatt 8 in Aufgabe 3a die Angabe, dass i∈N sein soll. Dies ist jetzt auch korrigiert.
Auf Blatt 8 in Aufgabe 3 waren in zwei Teilaufgaben die Sprachen fehlerhaft angegeben. In Aufgabe 3b fehlte die Angabe, dass x,y∈{a,b}^* sein soll. In Aufgabe 3c sollte w∈{a,b,c}^* sein und nicht w∈{a,b,c} ohne ^*. Das Aufgabenblatt wurde aktualisiert.
Auf Blatt 7 wurden zwei Kleinigkeiten verändert, bei bei Aufgabe 3. Da im Skript drei neue Beispiele dazugekommen sind, hat sich die Nummerierung verschoben. Daher bezieht sich die Aufgabe jetzt auf Hinweis 4.30, nicht mehr Hinweis 4.27. Außerdem waren P und S in der Definition von G vertauscht.
Der wegen Pfingstmontag ausfallende Übungstermin am Montag den 09.06.14 wird am darauffolgenden Freitag den 13.06.14 von 12:15 bis 13:45 in Raum 117 (Robert-Mayer-Str. 11-15) nachgeholt. Alternativ können Sie auch an der anderen Übungsgruppe am Dienstag den 10.06.14 von 12:15 bis 13:45 teilnehmen. Es war leider nicht möglich einen Alternativtermin zu finden, zu dem alle Teilnehmer der Montagsgruppe Zeit haben.
Die Übungsgruppe Montag 12:15 bis 13:45 wird nicht verlegt. Es wurde kein Alternativtermin gefunden, so dass mehr Personen an den Übungen teilnehmen können.
Da die Übungsgruppe Montag 12:15 bis 13:45 recht klein ist und einige Teilnehmer zu keinem der beiden Übungstermine Zeit habe, versuchen wir eine Alternativtermin für die Montagsgruppe zu finden. Wenn Sie in der Montagsgruppe eingetragen sind, dann folgen Sie bitte diesem Doodle-Link und tragen Sie die Termine ein zu denen Sie Zeit haben. In der Woche ab dem 12.05. findet die Übung garantiert noch Montag statt.
Die Videoaufzeichnugen der Vorlesung sind jetzt im Logbuch verlinkt.
In der ausgeteilten Version von Aufgabenblatt 1 befinden sich zwei kleine Fehler in den Hinweisen zu Aufgabe 3. In der aktuellen Version sind diese Fehler korrigiert. Anstatt L⊃Σ^* ist L⊂Σ^* korrekt und in der Gleichung direkt dahinter muss das rechte A ein L sein.
Übungsgruppenanmeldung: Die Anmeldung zu den Übungsgruppen fand in der ersten Vorlesung am 16. April statt. Nachträglich können Sie sich persönlich bei Joachim Bremer anmelden.
Die Vorlesung findet mittwochs, von 14:15 bis 17:00 Uhr im Magnus Hörsaal statt. Erster Vorlesungstermin war der 16. April. Erster Übungstermin war der 28./29. April.

Einführung

Die Vorlesung befasst sich mit Automaten und formalen Sprachen und gliedert sich im Wesentlichen in vier Teile:

Reguläre Sprachen,
kontextfreie Sprachen,
Chomsky-Hierarchie und
weiterführende Themen.

Charakterisierungen der regulären Sprachen durch deterministische und nichtdeterministische endliche Automaten sowie durch reguläre Ausdrücke werden als äquivalent nachgewiesen. Es werden Verfahren zur Minimierung endlicher Automaten entwickelt. Mit dem Pumping-Lemma werden die Grenzen der regulären Sprachen aufgezeigt.
Die kontextfreien Sprachen werden über kontextfreie Grammatiken eingeführt und anhand von Syntaxbäumen veranschaulicht. Pumping-Lemmata, Normalformen und Abschlusseigenschaften der kontextfreien Sprachen werden behandelt, und das Wortproblem für kontextfreie Sprachen wird algorithmisch gelöst. Es wird gezeigt, dass die kontextfreien Sprachen auch durch Kellerautomaten definiert werden können.
Im Anschluss daran wird die Chomsky-Hierarchie eingeführt und es werden insbesondere kontextsensitive Grammatiken und linear beschränkte Automaten betrachtet.
Als weiterführende Themen stehen u.A. zur Auswahl: Baumautomaten, erweiterte Grammatik-Modelle (z.B. programmierte Grammatiken), platzbeschränkte Komplexitätsklassen (z.B. PSPACE, LOGSPACE), Pattern-Matching-Algorithmen.

Kürzel laut Studienordnung: B-GL2. Creditpoints: 8. SWS: 3V, 2Ü.

Skript

Das Skript entsteht parallel zur Vorlesung. Die jeweils aktuelle Version erhalten Sie hier:

Logbuch

Hier finden Sie (nach den Vorlesungen) Informationen zum Inhalt der einzelnen Vorlesungsstunden, die in der Vorlesung verwendeten Folien und gelegentlich ergänzende Bemerkungen.

E-Lectures

Die Vorlesungen wurden von studiumdigitale, der E-Learning-Einrichtung der Goethe-Universität, auf Video aufgezeichnet und sind dort abrufbar. Direkte Links zu den einzelnen Aufzeichnungen finden Sie hier:

Vorlesung 1: Einführung, Organisatorisches, Grundbegriffe zum Thema Wörter und Sprachen. Klassen, Abschlusseigenschaften, Klasse FIN, Abschlusseigenschaften von FIN. Endliche Automaten und reguläre Sprachen - heute: DFAs, Klasse REG, Pumping-Lemma
[HTML5 | Flash | Quicktime | mobile | audio]
Vorlesung 2: Komplement- und Produktautomat, Abschlusseigenschaften, Nerode-Relation
[HTML5 | Flash | Quicktime | mobile | audio]
Vorlesung 3: Beweis Satz von Myhill-Nerode, Minimierung von DFAs
[HTML5 | Flash | Quicktime | mobile | audio]
Vorlesung 4 (Teil 1): NFAs
[HTML5 | Flash | Quicktime | mobile | audio]
Vorlesung 4 (Teil 2): NFAs mit nichtdeterministischem Startzustand, NFAs mit ε-Übergängen, Brzozowskis Algorithmus, Reversal-Konstruktion
[HTML5 | Flash | Quicktime | mobile | audio]
Vorlesung 5 (Teil 1): Abschluss der Klasse REG unter Vereinigung, Konkatenation und Kleene-Stern anhand von ε-NFAs, reguläre Ausdrücke, erweiterte NFAs
[HTML5 | Flash | Quicktime | mobile | audio]
Vorlesung 5 (Teil 2): Substitution, Homomorphismus und inverser Homomorphismus
[HTML5 | Flash | Quicktime | mobile | audio]
Vorlesung 6: Entscheidungsprobleme, reguläre Grammatiken. Kontextfreie Grammatiken, Abschlusseigenschaften, Ableitungsbäume.
[HTML5 | Flash | Quicktime | mobile | audio]
Vorlesung 7: Das Pumping-Lemma für Kontextfreie Sprachen, (Nicht-)Abschlusseigenschaften, Chomsky-Normalform
[HTML5 | Flash | Quicktime | mobile | audio]
Vorlesung 8: Der CYK-Algorithmus und Mehrdeutigkeit
[HTML5 | Flash | Quicktime | mobile | audio]
Vorlesung 9: Kellerautomaten (und der Abschluss der Klasse der kontextfreien Sprachen unter inversen Homomorphismen).
[HTML5 | Flash | Quicktime | mobile | audio]
Vorlesung 10: Deterministische Kellerautomaten (und deterministisch kontextfreie Sprachen), Entscheidungsprobleme für kontextfreie Sprachen (und das Postsche Korrespondenz Problem)
[HTML5 | Flash | Quicktime | mobile | audio]
Vorlesung 11: Wiederholung der Tripelkonstruktion. Kontextsensitive Sprachen (kontextsensitive und monotone Grammatiken, LBAs) und die Chomsky-Hierarchie.
[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. Die Folien finden Sie dort (Tripelkonstruktion) und dort (kontextsensitive Sprachen).
Vorlesung 12: Patternsprachen und erweiterte reguläre Ausdrücke.
[HTML5 | Flash | Quicktime | mobile | audio]
Vorlesung 13: XML, deterministische reguläre Ausdrücke und Glushkov-Automaten.
[HTML5 | Flash | Quicktime | mobile | audio]
Vorlesung 14: Pattern-Matching.
[HTML5 | Flash | Quicktime | mobile | audio]

Weitere Informationen zu den einzelnen Vorlesungen finden Sie im Logbuch.

Termine

	Zeit	Ort	Leitung
Vorlesung	Mittwoch 14:15-17:00 (vom 16.04.-16.07.)	Magnus-Hörsaal in der Informatik, Robert-Mayer-Str. 11-15	Dr. Dominik D. Freydenberger
Übung 1	Montag, 12:15-13:45	RMS 11-15, SR 307	Joachim Bremer
Übung 2	Dienstag, 12:15-13:45	RMS 11-15, SR 9	Sorin Constantinescu

Übungsblätter

Es wird regelmäßige Übungsaufgaben geben. Die Teilnahme an den Übungsstunden und das Bearbeiten der Übungsaufgaben ist für das Verständnis der Vorlesung und eine erfolgreiche Prüfung unbedingt empfohlen. Insbesondere kann durch die in den Übungen gesammelten Punkte ein Bonus für die Klausur erworben werden (Details siehe Klausur).

Das aktuelle Übungsblatt ist jeweils spätestens mittwochs nach der Vorlesung an dieser Stelle zu finden und wird außerdem mittwochs in gedruckter Form am Ende der Vorlesung ausgeteilt. Die Abgabe der bearbeiteten Übungsaufgaben erfolgt in der jeweils darauf folgenden Woche mittwochs, bis spätestens 14:14 Uhr vor Beginn der Vorlesung. Vorzeitig kann die Abgabe auch durch Einwurf in den Briefkasten neben Raum 114 (Robert-Mayer-Straße 11-15 1.Stock) erfolgen. Nach Beginn der Vorlesung werden keine Abgaben mehr entgegengenommen. Achtung: Auf dem abgegebenen Übungsblatt müssen Name, Matrikelnummer und Übungsgruppe vermerkt sein. Mehrseitige Abgaben sind zusammenzuheften. Die Abgabe erfolgt in Papierform (eine elektronische Abgabe ist aus logistischen Gründen leider nicht möglich).

Obwohl es sicherlich sinnvoll ist, über die Aufgaben mit Kommilitonen/innen gemeinsam zu reden und nachzudenken, sollte jede/r Student/in seine eigene Lösung aufschreiben und abgeben.

Übungsblatt 1 ( ausgeteilt am Mi, 16.04.2014 ; zu bearbeiten bis Mi, 23.04.2014 )
Übungsblatt 2 ( ausgeteilt am Mi, 23.04.2014 ; zu bearbeiten bis Mi, 30.04.2014 )
Übungsblatt 3 ( ausgeteilt am Mi, 30.04.2014 ; zu bearbeiten bis Mi, 07.05.2014 )
Übungsblatt 4 ( ausgeteilt am Mi, 07.05.2014 ; zu bearbeiten bis Mi, 14.05.2014 )
Übungsblatt 5 ( ausgeteilt am Mi, 14.05.2014 ; zu bearbeiten bis Mi, 21.05.2014 )
Übungsblatt 6 ( ausgeteilt am Mi, 21.05.2014 ; zu bearbeiten bis Mi, 28.05.2014 )
Übungsblatt 7 ( ausgeteilt am Mi, 28.05.2014 ; zu bearbeiten bis Mi, 04.06.2014 )
Übungsblatt 8 ( ausgeteilt am Mi, 04.06.2014 ; zu bearbeiten bis Mi, 11.06.2014 )
Übungsblatt 9 ( ausgeteilt am Mi, 11.06.2014 ; zu bearbeiten bis Mi, 18.06.2014 )
Übungsblatt 10 ( ausgeteilt am Mi, 18.06.2014 ; zu bearbeiten bis Mi, 25.06.2014 )
Übungsblatt 11 ( ausgeteilt am Mi, 25.06.2014 ; zu bearbeiten bis Mi, 02.07.2014 )
Übungsblatt 12 ( ausgeteilt am Mi, 02.07.2014 ; zu bearbeiten bis Mi, 09.07.2014 )
Übungsblatt 13 ( ausgeteilt am Mi, 16.07.2014 )
Übungsblatt 13 (mit Lösungen) ( ausgeteilt am Mo, 21.07.2014 )

Klausur

Termin:: Die Klausur (160 Minuten) findet am Dienstag, den 29.07.2014 von 10:00 bis 13:00 Uhr in Hörsaal V (Jügelhaus) statt.
Anmeldung:: Zur Teilnahme an der Klausur ist eine vorherige Anmeldung erforderlich.

Studierende der Studiengänge Bachelor-Informatik nach PO 06.12.2010 (neue Studienorordnung) und Bachelor-Bioinformatik melden sich bitte (1) im QIS/LSF-System der Goethe-Universtität und (2) per E-Mail bei Joachim Bremer mit dem Betreff "Klausuranmeldung" und den folgenden Informationen an: Name, Vorname, Matrikelnummer, genauer Studiengang (inkl. Studienordnung). Weitere Informationen erhalten Sie hier bzw. hier. Bitte stellen Sie sicher, dass Sie die Anmeldefristen nicht verpassen!

Studierende der Studiengänge Bachelor-Informatik nach PO 12.02.2007 (alte Studienordnung) melden sich bitte per E-Mail bei Joachim Bremer mit dem Betreff "Klausuranmeldung" und den folgenden Informationen an: Name, Vorname, Matrikelnummer, genauer Studiengang (inkl. Studienordnung).

Studierende anderer Studiengänge melden sich bitte (1) ggf. beim für sie zuständigen Prüfungsamt und (2) per E-Mail bei Joachim Bremer mit dem Betreff "Klausuranmeldung" und den folgenden Informationen an: Name, Vorname, Matrikelnummer, genauer Studiengang. Bei Studiengängen, bei denen wir einen schriftlichen Leistungsnachweis ausstellen (Schein), kann es sein, dass wir zusätzlich Ihr Geburtsdatum benötigen.
Benotung:: Durch die in den Übungen gesammelten Punkte kann ein Bonus für die Klausur erworben werden. Zur Benotung werden neben dem Klausurergebnis Bonuspunkte mit einem Maximalgewicht von 20% eingehen. Achtung: Die Bonuspunkte werden Ihnen für die Klausur nur unter der Bedingung gutgeschrieben, dass Sie mindestens einmal im Tutorium vorgerechnet haben.
Die Klausur ist bestanden, wenn mit dem Bonus mindestens 50% der in der Klausur erzielbaren Punkte erreicht werden.
Bei einem Ergebnis von x% aus der Klausur und y% aus den Übungen werden die folgenden Noten vergeben, wobei z = x + (20*y/100):
Weitere Details:: Weitere Details zur Anmeldung und zum Ablauf der Klausur folgen später.

Literatur

[RS]	G. Rozenberg und A. Salomaa. Handbook of Formal Languages, Vol. 1. Springer, 1997.
[S-GL2]	G. Schnitger. Skript zur Vorlesung "Formale Sprachen und Berechenbarkeit", Goethe-Universität Frankfurt am Main, Sommersemester 2013. Link
[S-DisMod]	N. Schweikardt. Skript zur Vorlesung "Diskrete Modellierung", Goethe-Universität Frankfurt am Main, 2013. Link
[W-Theo]	I. Wegener. Theoretische Informatik. Teubner, 2005 (3. Auflage).
[S-Comp]	M. Sipser. Introduction to the theory of computation. PWS Publishing, 2006 (2. Auflage).
[D-Dis]	V. Diekert, M. Kufleitner, G. Rosenberger, Diskrete algebraische Methoden. De Gruyter Studium, 2013.
[S-Sec]	J. Shallit. A Second Course in Formal Languages and Automata Theory. Cambridge University Press, 2008.
[HU]	J. E. Hopcroft and J.D. Ullman. Introduction to Automata Theory, Languages, and Computation. Addison-Wesley, 1979.
[W-Komp]	I. Wegener. Kompendium Theoretische Informatik - eine Ideensammlung. Teubner, 1996.
[S-Theo]	U. Schöning. Theoretische Informatik - kurzgefasst. Springer, 2001 (4. Auflage).