Theoretische Grundlagen der Informatik

Rolf Socher Theoretische Grundlagen der Informatik ISBN-10: 3-446-41260-3 ISBN-13: 978-3-446-41260-6 Vorwort Weitere Informationen oder Bestellungen unter http://www.hanser.de/978-3-446-41260-6 sowie im Buchhandel Vorwort Aus meiner eigenen Studienzeit erinnere ich mich an die Turing-Maschine als höchst abstraktes mathematisches Gebilde, dessen Funktionsweise nur sehr schwer zu verstehen war. In der Vorlesung wurden damals viele Tafeln mit langwierigen Berechnungsabläufen vollgeschrieben, was trotzdem wenig zum Verständnis bei- trug. Heute gibt es dagegen sehr viele und zum Teil auch sehr anspruchsvolle Simulatio- nen von Turing-Maschinen und anderen Konzepten der theoretischen Informatik, die man meist aus dem Internet herunterladen kann. Mit Hilfe einer solchen Visua- lisierung lässt sich die Arbeitsweise einer Turing-Maschine fast schon mit einem Blick begreifen. Es ist das Ziel dieses Buches und des Visualisierungssystemes „Machines“ auf der beiliegenden CD, die formale mathematische Strenge des Lehrbuchs mit der An- schaulichkeit des direkten Ausprobierens einer virtuellen Maschine zu verbinden. Dabei sind unter der einheitlichen Benutzungsoberfläche von „Machines“ alle klas- sischen Konzepte der theoretischen Informatik als Visualisierung verfügbar: endli- che Automaten, reguläre Ausdrücke, Kellerautomaten, Grammatiken und Turing- Maschinen. Das Buch richtet sich an Studierende der Informatik an Fachhochschulen und Uni- versitäten und eignet sich sowohl zum Selbststudium als auch zur vorlesungsbeglei- tenden Lektüre. Das „Machines“-System bietet neben der Möglichkeit des Auspro- bierens auch eine hervorragende Grundlage für ein vorlesungsbegleitendes Praktikum, in dem die vielfältigen Transformationen zwischen den verschiedenen Automatentypen, den Grammatiken und regulären Ausdrücken implementiert wer- den können. In den Aufgabenteilen der einzelnen Kapitel dieses Buches finden sich Vorschläge für Aufgabenstellungen für ein solches Praktikum. Für das bloße Aus- probieren der Automaten, Grammatiken und Turing-Maschinen sind keinerlei Vor- kennnisse erforderlich. Zur Implementierung von Transformationen werden Grund- kenntnisse der Programmiersprache Java erwartet. Für die sorgfältige Implementierung des „Machines“-Systems möchte ich mich be- sonders herzlich bei Cord Buhlert, Björn „Finne“ Mahn, Ralf Schmidt und Bodo Wenker bedanken. Andrea Baldas, Cord Buhlert, Thorsten Dunz, Ralf Schmidt und 5 Vorwort zur 3. Auflage Elisabeth Wolf haben das Manuskript sehr gründlich korrekturgelesen und das „Machines“-System ausgiebig getestet. Christian Märtin als Mitherausgeber der Reihe „Informatik interaktiv“ hat sehr hilfreiche inhaltliche und formale Korrekturvorschläge beigesteuert. Mein besonde- rer Dank gilt Erika Hotho von der Programmplanung des Fachbuchverlags Leipzig für ihren unermüdlichen Einsatz. Emden, im Juli 2003 Rolf Socher Vorwort zur 3. Auflage Auf vielfältigen Leserwunsch gibt es in der dritten Auflage nun auch die Lösungen zu den Aufgaben und einige Beweise. Ferner wurde der Anhang (mathematische Grundlagen) erweitert und vertieft sowie ebenfalls mit Aufgaben versehen. Im Unterschied zu den ersten beiden Auflagen liegt diesem Band keine CD mehr bei. Die Software „Machines“ finden Sie nun stattdessen im Internet unter der URL http://zeus.fh-brandenburg.de/~socher/tgi Ich danke Frau Juliane Andereggen für ihre großzügige Hilfe bei der Erstellung der Lösungen. Des Weiteren möchte ich allen Leserinnen und Lesern danken, die mich auf Fehler in der der ersten oder zweiten Auflage hingewiesen haben. Berlin, im September 2007 Rolf Socher 6

Rolf Socher Theoretische Grundlagen der Informatik ISBN-10: 3-446-41260-3 ISBN-13: 978-3-446-41260-6 Inhaltsverzeichnis Weitere Informationen oder Bestellungen unter http://www.hanser.de/978-3-446-41260-6 sowie im Buchhandel Inhalt 1 Einleitung ..............................................................................................................9 2 Endliche Automaten ..........................................................................................15 2.1 Einführung ....................................................................................................... 15 2.2 Grundlegende Begriffe ..................................................................................... 16 2.3 Deterministische endliche Automaten ............................................................ 18 2.4 Minimierung endlicher Automaten ................................................................. 23 2.5 Nichtdeterministische endliche Automaten ................................................... 29 2.6 Automaten mit ε -Übergängen ......................................................................... 35 2.7 Anwendung endlicher Automaten ................................................................... 39 3 Reguläre Sprachen .............................................................................................45 3.1 Reguläre Ausdrücke ......................................................................................... 45 3.2 Das Pumping-Lemma ...................................................................................... 52 3.3 Der Satz von Myhill-Nerode ............................................................................ 55 3.4 Abgeschlossenheitseigenschaften regulärer Sprachen .................................. 59 4 Grammatiken ......................................................................................................65 4.1 Grundlegende Definitionen ............................................................................. 66 4.2 Reguläre Grammatiken ................................................................................... 68 4.3 Kontextfreie Grammatiken ............................................................................. 74 4.4 Die Chomsky-Normalform und der CYK-Algorithmus .................................. 75 4.5 Eigenschaften kontextfreier Sprachen ............................................................ 82 4.6 Kellerautomaten ............................................................................................... 85 4.7 Kontextfreie Grammatiken und Kellerautomaten ......................................... 93 4.8 Typ-1- und Typ-0-Grammatiken ..................................................................... 96 4.9 Die Chomsky-Hierarchie ................................................................................. 97 5 Turing-Maschinen und Berechenbarkeit .......................................................101 5.1 Einführung ..................................................................................................... 101 5.2 Das Basismodell ............................................................................................. 103 5.3 Modifikationen des Basismodells .................................................................. 108 5.4 Linear beschränkte Automaten und Typ-1-Grammatiken .......................... 113 5.5 Die Sprachklassen der Chomsky-Hierarchie ................................................ 114 5.6 Turing-Berechenbarkeit ................................................................................ 116 5.7 Andere Berechnungskonzepte ....................................................................... 119 5.8 Die universelle Turing-Maschine .................................................................. 128 7 Inhalt 5.9 Die Churchsche These .................................................................................... 131 6 Entscheidbarkeit ..............................................................................................135 6.1 Entscheidbarkeit und Semi-Entscheidbarkeit ............................................. 135 6.2 Unentscheidbare Probleme ............................................................................ 140 6.3 Das Halteproblem .......................................................................................... 144 6.4 Reduktionstechniken ..................................................................................... 148 6.5 Der Satz von Rice ........................................................................................... 157 7 Komplexität ......................................................................................................159 7.1 Einführung ..................................................................................................... 159 7.2 Komplexität von Algorithmen ....................................................................... 161 7.3 Die Klassen P und NP .................................................................................... 168 7.4 NP-Vollständigkeit ......................................................................................... 178 8 Anhang: Mathematische Grundlagen ............................................................187 8.1 Mengen ........................................................................................................... 187 8.2 Partitionen ...................................................................................................... 189 8.3 Relationen ....................................................................................................... 189 8.4 Graphen .......................................................................................................... 194 8.5 Aussagenlogik ................................................................................................. 195 Lösungen der Aufgaben .............................................................................................201 Literatur .......................................................................................................................223 Register ........................................................................................................................225 8

Rolf Socher Theoretische Grundlagen der Informatik ISBN-10: 3-446-41260-3 ISBN-13: 978-3-446-41260-6 Leseprobe Weitere Informationen oder Bestellungen unter http://www.hanser.de/978-3-446-41260-6 sowie im Buchhandel 2 Endliche Automaten 2 2.1 Einführung Viele Dinge des täglichen Lebens lassen sich als Automaten auffassen, die verschie- dene Zustände einnehmen können. Betrachten wir etwa eine U-Bahn-Eintrittskon- trolle 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 entrie- gelten Zustand. Durch Drehung der Arme geht das Gerät in den verriegelten Zu- stand zurück. Die beiden möglichen Aktionen sind das Einwerfen eines Chips und das Drehen der Arme. Chip verriegelt entriegelt drehen drehen Chip Abbildung 2.1: Der U-Bahn-Automat 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 Zu- stand über. Im entriegelten Zustand ist das Einwerfen eines weiteren Chips dage- gen 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änke- oder Zigarettenautomaten bestens bekannt, also Geräte, die bei Einwurf eines be- stimmten 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 AP kann zur Paritätsprüfung verwendet werden. Die Eingabe besteht aus einer Reihe von Binär- ziffern. Der Automat prüft, ob diese eine gerade oder ungerade Anzahl von Einsen 15 2 Endliche Automaten start 1 gerade ungerade 0 1 0 Abbildung 2.2: Der Automat AP zur Paritätsprüfung 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 Be- schriftung „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 be- stimmten Bedingung genügt (beispielsweise die Bedingung gerader Parität). Zu die- sem Zweck führt man so genannte akzeptierende Zustände ein (auch Endezustände genannt), in unserem Beispiel den Zustand „gerade“. In der graphischen Darstel- lung werden akzeptierende Zustände mit doppelt umrandeten Knoten gekennzeich- net. Befindet sich der Automat nach der Verarbeitung der Eingabe in einem akzep- tierenden 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. 2.2 Grundlegende Begriffe Ein Alphabet ist eine endliche, nicht leere Menge, deren Elemente Zeichen genannt werden. Ein Zeichen ist eine formale Einheit, die nicht näher definiert wird. Übli- cherweise sind dies Ziffern, Buchstaben oder Sonderzeichen. Die Einschränkung, dass ein Alphabet nicht leer sein darf, wird getroffen, um von vornherein Sonderfälle, die sich aus einem leeren Alphabet ergeben könnten, auszu- schließen. Alphabete werden grundsätzlich mit dem Buchstaben Σ bezeichnet. Ein Wort (über einem Alphabet Σ ) ist eine endliche Folge von Zeichen aus Σ . Sind zum Beispiel a, b, c Zeichen, so lassen sich daraus Wörter wie cba oder aaab bilden. Das leere Wort wird mit ε bezeichnet. Die Menge aller Wörter, die mit Zeichen aus Σ gebildet werden können, wird mit Σ * bezeichnet. Die Länge eines Wortes w ist die Anzahl der in w vorkommenden Zeichen. Sie wird mit | w| bezeichnet. Ist etwa w = aabac, so ist | w| = 5. Formal lässt sich | w| rekursiv definieren durch die folgende Vorschrift: 16 2.2 Grundlegende Begriffe |ε| =0 | aw| = 1 + | w| , falls a ∈ Σ , w ∈ Σ *. Diese rekursive Definition zeigt beispielhaft das allgemeine Muster der rekursiven Definition einer Funktion f, die auf der Menge Σ * aller Wörter definiert ist. Die erste Zeile der Definition legt den Funktionswert f(ε ) fest. Die zweite Zeile definiert den Funktionswert für ein Wort aw, dessen erstes Zeichen a ist. In der Definition dieses Funktionswertes dürfen sowohl a und w als auch der Wert f(w) rekursiv verwendet werden. Ist w ein Wort über dem Alphabet Σ und a ein Zeichen aus Σ , so bezeichnet | w| a die Anzahl der Vorkommen des Zeichens a in w. Ist etwa w = element, so ist | w| e = 3, | w| m = 1 und | w| x = 0. Die Konkatenation zweier Wörter ist das Wort, das sich ergibt, wenn man die beiden Wörter direkt hintereinander schreibt. So ergibt die Konkatenation der Wörter Auto und mat das Wort Automat. Manchmal benutzt man zur Verdeutlichung einen ex- pliziten Konkatenationsoperator in Form eines Malpunktes. Man kann also auch v .w statt vw schreiben. Das leere Wort ist das neutrale Element der Konkatenation, d.h. für jedes Wort w gilt ε w = wε = w. Ähnlich wie bei Zahlen verwendet man eine Potenzschreibweise für das mehrfache Konkatenieren von Wörtern. So schreibt man etwa vereinfachend a4 für das Wort aaaa oder (ab)3 für das Wort ababab. Allgemein definiert man für ein beliebiges Wort w: w0 = ε wn = w . wn–1 , falls n > 0. Ist w ein Wort über einem Alphabet Σ , so bezeichnet wT die Spiegelung von w. Ist etwa w = automat, so ist wT = tamotua. Eine Sprache über einem Alphabet Σ ist eine Menge von Wörtern über Σ . Sprachen werden grundsätzlich mit dem Buchstaben L (engl. language), gegebenenfalls mit Indizes, bezeichnet. Spezielle Sprachen sind die leere Menge, die Menge Σ * sowie die Menge {ε} , die nur das leere Wort enthält. Beispiel 2.1: a) Beim U-Bahn-Automaten wird das Alphabet Σ = { „Chip“, „drehen“} verwendet. Man beachte, dass das ganze Wort „Chip“ als Eingabezeichen defi- niert ist und nicht die einzelnen Zeichen C, h, i und p. Ein Zeichen stellt somit die kleinste unabhängige und unteilbare Einheit der Eingabe dar. b) Der Automat AP zur Paritätsprüfung verwendet das Alphabet Σ = { 0, 1} . Sprachen über Σ sind etwa die Mengen { 0, 10, 0011} oder {ε , 01, 0011, 000111,… } = { 0n 1n | n ≥ 0} . 17 2 Endliche Automaten Da Sprachen Mengen sind, sind auf ihnen die Mengenoperationen ∪ , ∩ usw. defi- niert. Darüber hinaus wird die Konkatenation zweier Sprachen L1 und L2 folgender- maßen definiert: L1 L2 = { vw | v ∈ L1, w ∈ L2 } . Ist etwa Σ = { 0, 1} , L1 = { 0, 00} und L2 = { 1, 11} , so ist L1L2 = { 01, 011, 001, 0011} . Ist L eine Sprache, so ist Ln definiert als die n-fache Konkatenation von L mit sich selbst, also L0 = {ε} Ln = L . Ln–1 , falls n > 0. Die Kleenesche Hülle L* der Sprache L ist folgendermaßen definiert: L∗ = ∪ Ln n≥0 2.3 Deterministische endliche Automaten Definition des DEA Der U-Bahn-Automat und der Automat zur Paritätsprüfung lassen sich jeweils auch in Tabellenform darstellen. Tabelle 2.1: Automat zur Paritätsprüfung δ 0 1 gerade/E gerade ungerade ungerade ungerade gerade Tabelle 2.1 zeigt, dass der Automat vom Zustand „gerade“ bei Eingabe einer 1 in den Zustand „ungerade“ übergeht. Die Tabelle lässt sich auch durch eine Funktion δ be- schreiben, die einem Zustand und einem Zeichen jeweils einen Folgezustand zuord- net, also δ (gerade, 1) = ungerade usw. Der Zustand „gerade“ ist mit /E als Endezu- stand gekennzeichnet. Ein deterministischer endlicher Automat (im Folgenden schreiben wir meist kurz „Automat“ statt „deterministischer endlicher Automat“) besteht also aus einem Al- phabet Σ , das die zulässigen Eingabezeichen auflistet, einer endlichen Menge Z von Zuständen und einer Vorschrift δ , die die Zustandsübergänge beschreibt.