Theoretische Grundlagen der Informatik (eBook)

Vorwort 6
Inhalt 8
1 Einleitung 10
2 Endliche Automaten 16
2.1 Einführung 16
2.2 Grundlegende Begriffe 17
2.3 Deterministische endliche Automaten 19
2.4 Minimierung endlicher Automaten 24
2.5 Nichtdeterministische endliche Automaten 30
2.6 Automaten mit e-Übergängen 36
2.7 Anwendung endlicher Automaten 40
3 Reguläre Sprachen 46
3.1 Reguläre Ausdrücke 46
3.2 DasPumping-Lemma 53
3.3 Der SatzvonMyhill-Nerode 56
3.4 Abgeschlossenheitseigenschaften regulärer Sprachen 60
4 Grammatiken 66
4.1 Grundlegende Definitionen 67
4.2 Reguläre Grammatiken 69
4.3 KontextfreieGrammatiken 75
4.4 DieChomsky-Normalform und der CYK-Algorithmus 76
4.5 Eigenschaftenkontextfreier Sprachen 83
4.6 Kellerautomaten 86
4.7 KontextfreieGrammatiken und Kellerautomaten 94
4.8 Typ-1- und Typ-0-Grammatiken 97
4.9 DieChomsky-Hierarchie 98
5 Turing-Maschinen und Berechenbarkeit 102
5.1 Einführung 102
5.2 DasBasismodel 104
5.3 Modifikationen des Basismodells 109
5.4 Linear beschränkte Automaten und Typ-1-Grammatiken 114
5.5 DieSprachklassen der Chomsky-Hierarchie 115
5.6 Turing-Berechenbarkeit 117
5.7 Andere Berechnungskonzepte 120
5.8 Die universelle Turing-Maschine 129
5.9 Die Churchsche These 132
6 Entscheidbarkeit 136
6.1 Entscheidbarkeit und Semi-Entscheidbarkeit 136
6.2 UnentscheidbareProbleme 141
6.3 DasHalteproblem 145
6.4 Reduktionstechniken 149
6.5 Der Satzvon Rice 158
7 Komplexität 160
7.1 Einführung 160
7.2 Komplexität vonAlgorithmen 162
7.3 Die Klassen P und NP 169
7.4 NP-Vollständigkeit 179
8 Anhang: Mathematische Grundlagen 188
8.1 Mengen 188
8.2 Partitionen 190
8.3 Relationen 190
8.4 Graphen 195
8.5 Aussagenlogik 196
Lösungen der Aufgaben 202
Register 226

2 Endliche Automaten (S. 15-16)

2.1 Einführung

Viele Dinge des täglichen Lebens lassen sich als Automaten auffassen, die verschiedene Zustände einnehmen können. Betrachten wir etwa eine U-Bahn-Eintrittskontrolle mit drei stählernen Armen. Dieses Gerät befindet sich stets in einem der zwei Zustände „verriegelt" und „entriegelt". Im verriegelten Zustand lassen sich die Arme nicht drehen. Wirft man nun einen Chip ein, so gibt ein Mechanismus die Arme frei. Die Eingabe eines Chips bewirkt also den Übergang vom verriegelten in den entriegelten Zustand. Durch Drehung der Arme geht das Gerät in den verriegelten Zustand zurück. Die beiden möglichen Aktionen sind das Einwerfen eines Chips und das Drehen der Arme.

Das Verhalten des Gerätes hängt offenbar sowohl von der Aktion (Chip einwerfen oder Arme drehen) als auch von seinem jeweiligen Zustand ab. Abbildung 2.1 zeigt die möglichen Zustandsübergänge: Im verriegelten Zustand bewirkt das Drehen der Arme nichts, während das Einwerfen eines Chips die Sperre entriegelt. Werden im entriegelten Zustand die Arme gedreht, so geht das Gerät in den verriegelten Zustand über. Im entriegelten Zustand ist das Einwerfen eines weiteren Chips dagegen sinnlos, die Sperre bleibt entriegelt. Man bezeichnet ein solches Gerät, das in Abhängigkeit vom aktuellen Zustand und von der jeweiligen Aktion bzw. Eingabe in einen anderen Zustand übergeht, als Automaten. Aus dem Alltag sind Getränkeoder Zigarettenautomaten bestens bekannt, also Geräte, die bei Einwurf eines bestimmten Betrags eine Ware ausgeben.

In der Informatik werden Automaten hauptsächlich verwendet, um Zeichenfolgen auf ihre Plausibilität zu prüfen. Der in Abbildung 2.2 gezeigte Automat A P kann zur Paritätsprüfung verwendet werden. Die Eingabe besteht aus einer Reihe von Binärziffern. Der Automat prüft, ob diese eine gerade oder ungerade Anzahl von Einsen enthält. Der Ablauf beginnt im Zustand „gerade", weil am Anfang noch keine Einsen gelesen wurden und 0 eine gerade Zahl ist. Dies wird durch den Pfeil mit der Beschriftung „start" angedeutet. Liest der Automat eine Null, so bleibt er im jeweiligen Zustand („gerade" bzw. „ungerade"), liest er eine Eins, so wechselt er von „gerade" nach „ungerade" bzw. von „ungerade" nach „gerade".

Hat der Automat das Eingabewort vollständig gelesen, so zeigt der Zustand, in dem er sich dann befindet, ob das Eingabewort gerade oder ungerade Parität hat. Im Allgemeinen prüft man mit Hilfe eines Automaten, ob die Eingabe einer bestimmten Bedingung genügt (beispielsweise die Bedingung gerader Parität). Zu diesem Zweck führt man so genannte akzeptierende Zustände ein (auch Endezustände genannt), in unserem Beispiel den Zustand „gerade". In der graphischen Darstellung werden akzeptierende Zustände mit doppelt umrandeten Knoten gekennzeichnet. Befindet sich der Automat nach der Verarbeitung der Eingabe in einem akzeptierenden Zustand, so bedeutet dies, dass die Eingabe akzeptiert wird.

In den beiden genannten Beispielen kann die Eingabe als ein Wort, also als Folge von Zeichen aufgefasst werden. Im folgenden Abschnitt sollen zunächst die daraus resultierenden Grundbegriffe wie Zeichen, Wörter und Sprachen definiert werden.