Grundlagen Theoretischer Informatik I / II

Grundlagen Theoretischer Informatik I / II

Wintersemester 2005/2006 — Dr. Norbert Müller — Universität Trier Basis: Skripten zur Vorlesung Informatik-B2 an der Universität Duisburg-Essen (Prof. Luther, Prof. Hertling)

Inhaltsverzeichnis

1 Formale Sprachen – Grundlagen 1.1 1.2 1.3 2 Einige Definitionen und Grundlagen . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Chomsky-Hierarchie . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4 4 9 13 15 15 22 28 33 38 40 42 43 43 47 50 51 54 62 63 72 72 75 79 86 93 95

Wortproblem . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

Reguläre Sprachen 2.1 2.2 2.3 2.4 2.5 2.6 2.7 Deterministische endliche Automaten . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Nichtdeterministische Automaten . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

Reguläre Ausdrücke und Sprachen . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Der Minimalautomat . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

Das Pumping-Lemma . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Abschlusseigenschaften und Entscheidbarkeit . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Anwendungen endlicher Automaten . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

---

Kontextfreie und andere Sprachen 3.1 3.2 3.3 3.4 3.5 3.6 3.7 Normalformen . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Das Pumping-Lemma für kontextfreie Sprachen . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Abschlusseigenschaften kontextfreier Sprachen . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Entscheidbarkeit bei kontextfreien Sprachen . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Kellerautomaten . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

Deterministisch kontextfreie Sprachen . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Kontextsensitive und Typ-0-Sprachen . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

---

Berechenbarkeit 4.1 4.2 4.3 4.4 4.5 4.6 4.7 4.8 4.9 Intuitiver Berechenbarkeitsbegriff und Church’sche These . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Berechenbarkeit mittels Turingmaschinen . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . LOOP-, WHILE- und GOTO-Berechenbarkeit . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Primitiv rekursive und µ-rekursive Funktionen . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

Eine totale WHILE-, aber nicht LOOP-berechenbare Funktion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Standardnotationen für berechenbare Funktionen Entscheidbarkeit und rekursive Aufzählbarkeit . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 100

Das Postsche Korrespondenzproblem . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 106 Unentscheidbare Grammatikprobleme . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 110

4.10 Der Gödelsche Satz . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 113

5

Komplexitätstheorie 5.1 5.2 5.3

115

Komplexitätsklassen und das P -N P -Problem . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 115 NP-Vollständigkeit . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 119 Weitere NP-vollständige Probleme . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 124

---

Literatur

[1] Uwe Schöning: Theoretische Informatik – kurzgefasst, 4. Auflage. Spektrum, Heidelberg 2001 [2] John E. Hopcroft, Jeffrey D. Ullman: Introduction to Automata Theory, Languages and Computation, Addison-Wesley, Reading, Massachusetts, 1979 (Einführung in die Automatentheorie, formale Sprachen und Komplexitätstheorie, OldenbourgVerlag, München, 2000).

Organisatorisches • Vorlesung: Donnerstag, 10-12, HS 13 • Übung: Donnerstag, 12-14, HS 11 • Sprechstunde: Di, 14-16, Do 14-16, H439 • Leistungsnachweis: 40% der Punkte der Übungen, sowie Klausur/mdl.Prüfung, voraussichtlich am letzten Vorlesungstermin • Folien/Skript/Übungsaufgaben zur Vorlesung: www.informatik.uni-trier.de/ mueller/Lehre/2005-bbkeit/ bzw. unter studip.uni-trier.de

---