Formale Sprachen

Vorlesung

Mo 11-13h, AM, HS 134
Do 11-13h, AM, HS - 101
Priv.-Doz. Dr. Wolfgang Merkle
INF 294, Zimmer 005
Telefon: 06221/54-5409
email: merkle@math.uni-heidelberg.de
Sprechstunde: Mo ab 14h und nach Vereinbarung
(in der vorlesungsfreien Zeit nach Vereinbarung)

Aktuelles

Inhalt

In der Vorlesung wird eine Einführung in die Theorie der Formalen Sprachen und die Automatentheorie gegeben. Diese zentralen Teilbereiche der Theoretischen Informatik sind eng verbunden mit der Berechenbarkeits- und Komplexitätstheorie und dienen als eine der Grundlagen für den Compilerbau und die Theorie der Programmierung. Themen: Die Sprachklassen der Chomsky-Hierarchie werden in der Vorlesung ausführlich behandelt werden. Hierbei werden Ausdrucksstärke, Abschlusseigenschaften, Entscheidbarkeitsfragen, Normalformen und Mschinencharakterisierungen erörtert werden.

Übungen

Mo 14h, AM, HS - 101

Tutor

Michael Kuhn

Übungsaufgaben

Hier finden Sie die aktuellen Übungsaufgaben. Übungsblatt 1 vom 13.10.2008 [PDF]
Übungsblatt 2 vom 20.10.2008 [PDF]
Übungsblatt 3 vom 27.10.2008 [PDF]
Übungsblatt 4 vom 3.11.2008 [PDF]
Übungsblatt 5 vom 10.11.2008 [PDF]
Übungsblatt 6 vom 17.11.2008 [PDF]
Übungsblatt 7 vom 24.11.2008 [PDF]
Übungsblatt 8 vom 1.12.2008 [PDF]
Übungsblatt 9 vom 8.12.2008 [PDF]
Übungsblatt 10 vom 15.12.2008 [PDF]
Übungsblatt 11 vom 12.1.2009 [PDF]

Zielgruppe

Studierende der Mathematik, Informatik und Computerlinguistik

Voraussetzungen

Spezielle Vorkenntnisse werden nicht vorausgesetzt.

Literatur und Skripten

Dexter Kozen, Automata and Computability, Springer 1997.
John Hopcroft, Rajeev Motwani und Jeffrey Ullman, Einführung in die Automatentheorie, Formale Sprachen und Komplexitätstheorie, Pearson 2002
(Übersetzung von "Introduction to Automata Theory, Languages and Computation", Addison-Wesley 2001)