Theoretische Informatik 2

Vorlesung

Einführung

Die Vorlesung befasst sich mit Automaten und formalen Sprachen und gliedert sich im Wesentlichen in vier Teile: 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:

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.