"Informatik III 001.ps.gz" - читать интересную книгу автора

Informatik III Prof. Dr. H. Prautzsch Skript zur Vorlesung gehalten im Winter 1999/2000

2 Inhaltsverzeichnis I Formale Sprachen 7 1 Sprachen und Grammatiken 9

1.1 Grundbegriffe . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9 1.2 Grammatiken . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10 1.3 Chomsky-Hierarchie . . . . . . . . . . . . . . . . . . . . . . . . . 11 1.4 Abschlusseigenschaften . . . . . . . . . . . . . . . . . . . . . . . . 12

2 Regula"re Sprachen 15

2.1 Deterministische endliche Akzeptoren . . . . . . . . . . . . . . . 15 2.2 Nichtdeterministische endliche Automaten . . . . . . . . . . . . . 16 2.3 Das Pump-Lemma . . . . . . . . . . . . . . . . . . . . . . . . . . 18 2.4 Regula"re Ausdru"cke . . . . . . . . . . . . . . . . . . . . . . . . . 19 2.5 Eine A"quivalenzrelation . . . . . . . . . . . . . . . . . . . . . . . 20 2.6 Der Minimalautomat . . . . . . . . . . . . . . . . . . . . . . . . . 22 2.7 Abschlusseigenschaften . . . . . . . . . . . . . . . . . . . . . . . . 24 2.8 Entscheidbare Probleme . . . . . . . . . . . . . . . . . . . . . . . 24

3 Kontextfreie Sprachen 25

3.1 Syntaxba"ume . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25 3.2 Das Pump-Lemma . . . . . . . . . . . . . . . . . . . . . . . . . . 26 3.3 Einfache Kellerautomaten . . . . . . . . . . . . . . . . . . . . . . 28 3.4 Einfache Kellerautomaten u. kontextfr. Sprachen . . . . . . . . . 29 3.5 Allgemeine Kellerautomaten . . . . . . . . . . . . . . . . . . . . . 30 3.6 Chomsky Normalform . . . . . . . . . . . . . . . . . . . . . . . . 32 3.7 Cocke-Kasami-Younger-Algorithmus . . . . . . . . . . . . . . . . 33 3.8 Abschlusseigenschaften . . . . . . . . . . . . . . . . . . . . . . . . 35 3.9 Entscheidbare Probleme . . . . . . . . . . . . . . . . . . . . . . . 36

4 Sprachen vom Typ 0 und 1 39

4.1 Kontextsensitive Grammatiken . . . . . . . . . . . . . . . . . . . 39 4.2 Turingmaschinen . . . . . . . . . . . . . . . . . . . . . . . . . . . 40 4.3 Ein Beispiel . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 41 4.4 Linear beschra"nkte Turing-Maschine . . . . . . . . . . . . . . . . 42 4.5 Deterministische Turingmaschinen . . . . . . . . . . . . . . . . . 44 4.6 Abschlusseigenschaften . . . . . . . . . . . . . . . . . . . . . . . . 44 4.7 Das Halteproblem . . . . . . . . . . . . . . . . . . . . . . . . . . 45 4.8 Das Wortproblem . . . . . . . . . . . . . . . . . . . . . . . . . . . 46 4.9 Das Postsche Korrespondenzproblem . . . . . . . . . . . . . . . . 47

3

4 INHALTSVERZEICHNIS

4.10 (Un)entscheidbare Probleme . . . . . . . . . . . . . . . . . . . . . 48 5 Fixpunkttheorie 51

5.1 Halbordnungen . . . . . . . . . . . . . . . . . . . . . . . . . . . . 51 5.2 Ein Fixpunkttheorem . . . . . . . . . . . . . . . . . . . . . . . . 53 5.3 Kontextfreie Sprachen als Fixpunkte . . . . . . . . . . . . . . . . 56 5.4 Gleichungssysteme . . . . . . . . . . . . . . . . . . . . . . . . . . 57

6 Syntaxanalyse 59

6.1 Einfu"hrende Beispiele . . . . . . . . . . . . . . . . . . . . . . . . 59 6.2 SLL(k)-Grammatiken . . . . . . . . . . . . . . . . . . . . . . . . 60 6.3 LR(k)-Grammatiken . . . . . . . . . . . . . . . . . . . . . . . . . 62 6.4 LR(k)-Analyse . . . . . . . . . . . . . . . . . . . . . . . . . . . . 63 6.5 Linke Kontexte . . . . . . . . . . . . . . . . . . . . . . . . . . . . 64 6.6 Kontextmengen . . . . . . . . . . . . . . . . . . . . . . . . . . . . 65 6.7 Kellerautomaten fu"r LR(k)-Grammatiken . . . . . . . . . . . . . 67

II Berechenbarkeitstheorie 69 7 Berechenbarkeitstheorie 71

7.1 Intuitiver Berechenbarkeitsbegriff . . . . . . . . . . . . . . . . . . 71 7.2 Turing-Berechenbarkeit . . . . . . . . . . . . . . . . . . . . . . . 72 7.3 loop- und while-Berechenbarkeit . . . . . . . . . . . . . . . . . . 73 7.4 Makros . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 74 7.5 Vergleich von while- und Turing-Berechenbarkeit . . . . . . . . . 76 7.6 goto-Programme . . . . . . . . . . . . . . . . . . . . . . . . . . . 77 7.7 Zusammenfassung . . . . . . . . . . . . . . . . . . . . . . . . . . 78 7.8 Die Ackermannfunktion . . . . . . . . . . . . . . . . . . . . . . . 78

8 Universelle Funktionen 81

8.1 Aufza"hlung der while-Programme . . . . . . . . . . . . . . . . . 81 8.2 Indexu"berpru"fung . . . . . . . . . . . . . . . . . . . . . . . . . . . 82 8.3 Kompakte while-Programme . . . . . . . . . . . . . . . . . . . . 83 8.4 Der Interpreter . . . . . . . . . . . . . . . . . . . . . . . . . . . . 84