Theoretische Informatik 2

Vorlesung

• Theoretische Informatik 2 im SoSe 2014 (Aktuelles Semester)
• Theoretische Informatik 2 im SoSe 2012

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Ü.

E-Lectures

Im Sommersemester 2012 wurden die Vorlesungen von studiumdigitale, der E-Learning-Einrichtung der Goethe-Universität, auf Video aufgezeichnet. Die einzelnen Aufzeichnungen finden Sie hier:

• Kapitel 1: Einführung ins Thema [Flash | QuickTime | Mobile | MP3] (Aufzeichnung vom 12.04.2012)
• Kapitel 2: Endliche Automaten und reguläre Sprachen
  1. Teil 1: DFAs, NFAs und Mealy Automaten [Flash | QuickTime | Mobile | MP3] (Aufzeichnung vom 12.04.2012)
  2. Teil 2: DFA-Minimierung [Flash | QuickTime | Mobile | MP3] (Aufzeichnung vom 19.04.2012)
  3. Teil 3: Der Satz von Myhill-Nerode und das Pumping Lemma [Flash | QuickTime | Mobile | MP3] (Aufzeichnung vom 26.04.2012)
  4. Teil 4: Untere Schranken für die Größe von NFAs, NFAs mit epsilon-Übergängen, Abschlusseigenschaften der Klasse aller regulären Sprachen [Flash | QuickTime | Mobile | MP3] (Aufzeichnung vom 03.05.2012)
  5. Teil 5: Homomorphismen, Anwendung der Abschlusseigenschaften der Klasse aller regulären Sprachen, Entscheidungsprobleme, reguläre Ausdrücke [Flash | QuickTime | Mobile | MP3] (Aufzeichnung vom 10.05.2012)
  6. Teil 6: Der Satz von Kleene, reguläre Ausdrücke für Komplement und Durchschnitt, reguläre Grammatiken [Flash | QuickTime | Mobile | MP3] (Aufzeichnung vom 24.05.2012)
• Kapitel 3: Kontextfreie Sprachen
  1. Teil 1: Beispiele für kontextfreie Grammatiken [Flash | QuickTime | Mobile | MP3] (Aufzeichnung vom 24.05.2012)
  2. Teil 2: Kontextfreie Grammatiken für Programmiersprachen; Ableitungsbäume und eindeutige Grammatiken; Pumping Lemma und Ogden's Lemma [Flash | QuickTime | Mobile | MP3] (Aufzeichnung vom 31.05.2012)
  3. Teil 3: Beweis von Odgen's Lemma; Abschlusseigenschaften der Klasse aller kontextfreien Sprachen; Kellerautomaten [Flash | QuickTime | Mobile | MP3] (Aufzeichnung vom 14.06.2012)
  4. Teil 4: Äquivalenz zwischen Kellerautomaten und kontextfreien Sprachen; deterministisch kontextfreie Sprachen; der CYK-Algorithmus [Flash | QuickTime | Mobile | MP3] (Aufzeichnung vom 21.06.2012)
• Kapitel 4: Berechenbarkeit
  1. Teil 1: Halteproblem, (Semi-)Entscheidbarkeit, Rekursive Aufzählbarkeit, Berechenbarkeit, Satz von Rice, Turingmaschinen [Flash | QuickTime | Mobile | MP3] (Aufzeichnung vom 02.07.2012)
  2. Teil 2: (Mehrband-)Turingmaschinen, Church-Turing-These, Gödelnummern, universelle Turingmaschine, Reduktionen, Unentscheidbarkeit der Diagonalsprache und der universellen Sprache [Flash | QuickTime | Mobile | MP3] (Aufzeichnung vom 05.07.2012)
  3. Teil 3: Unentscheidbarkeit des Halteproblems und des speziellen Halteproblems, Unentscheidbarkeit des Postschen Korrespondenzproblems, unentscheidbare Grammatik-Probleme [Flash | QuickTime | Mobile | MP3] (Aufzeichnung vom 12.07.2012)
• Kapitel 5: Die Chomsky Hierarchie [Flash | QuickTime | Mobile | MP3] (Aufzeichnung vom 12.07.2012)
• Zusammenfassung der wichtigsten in Vorlesung und Übung behandelten Themen sowie Hilfestellungen zur Klausurvorbereitung [Flash | QuickTime | Mobile | MP3] (Aufzeichnung vom 19.07.2012)

Literatur

[S-GL2]	G. Schnitger. Skript zur Vorlesung "Formale Sprachen und Berechenbarkeit", Goethe-Universität Frankfurt am Main, Sommersemester 2011. Link
[S-DisMod]	N. Schweikardt. Skript zur Vorlesung "Diskrete Modellierung", Goethe-Universität Frankfurt am Main, 2011. Link
[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.
[W-Theo]	I. Wegener. Theoretische Informatik. Teubner, 1999 (2. Auflage).
[S-Theo]	U. Schöning. Theoretische Informatik - kurzgefasst. Springer, 2001 (4. Auflage).
[S-Comp]	M. Sipser. Introduction to the theory of computation. PWS Publishing, 1997.