Autorentext
Roland Schmitz ist promovierter Mathematiker und seit 2001 Professor für Internet-Security im Studiengang Medieninformatik an der Hochschule der Medien in Stuttgart. Vorher war er sechs Jahre lang wissenschaftlicher Mitarbeiter am Technologiezentrum der Deutschen Telekom mit den Hauptarbeitsgebieten Sicherheit mobiler Kommunikation sowie Standardisierung digitaler Signaturen.
Inhalt
Über den Autor 7
Einleitung 17
Was ist theoretische Informatik? 17
Über dieses Buch 18
Wie dieses Buch aufgebaut ist 18
Symbole in diesem Buch 20
Wie Sie dieses Buch lesen sollten 20
Teil I Endliche Automaten 21
Kapitel 1 Deterministische Endliche Automaten (DFAs) 23
Einführung 23
Erste Beispiele 24
Grundlegende Definitionen 27
Symbole und Wörter 27
Die Definition eines DFAs 28
Reguläre Sprachen 30
Die erweiterte Übergangsfunktion 30
Beispiele regulärer Sprachen 31
Das Pumping Lemma 34
Minimalautomaten 38
Der Satz von Myhill und Nerode 45
DFAs mit Ausgabe (Moore- und Mealy-Automaten) 50
Aufgaben zu DFAs 54
Kapitel 2 Nichtdeterministische Endliche Automaten (NFAs) 57
Nichtdeterminismus 57
Definition eines NFA 58
Der Satz von Rabin-Scott 60
NFAs mit 𝜖-Übergängen 64
Abschlusseigenschaften regulärer Sprachen 67
Reguläre Ausdrücke 70
Stochastische Automaten und Markov-Ketten 75
Hidden Markov Models 80
Aufgaben zu NFAs 80
Kapitel 3 Kellerautomaten (PDAs) 83
Nichtdeterministische Kellerautomaten 83
Deterministische Kellerautomaten 89
Die Grenzen von PDAs 91
Aufgaben zu PDAs 92
Kapitel 4 Turing-Maschinen 93
Deterministische Turing-Maschinen 93
Turing-Berechenbarkeit 102
Mehrband-Turing-Maschinen 105
Registermaschinen 109
Nichtdeterministische Turing-Maschinen 110
Linear beschränkte Turing-Maschinen 112
Universelle Turing-Maschine (UTM) 113
Die Grenzen von Turing-Maschinen 115
Aufgaben zu Turing-Maschinen 120
Teil II Formale Sprachen 123
Kapitel 5 Grammatiken 125
Einführung 125
Ein erstes Beispiel 126
Syntaxbäume 127
Definition einer Grammatik 128
Die von einer Grammatik erzeugte Sprache 128
Wie man 𝜖-Regeln loswird 129
Das Wortproblem 131
Chomsky-Hierarchie 131
Aufgaben zu Grammatiken 133
Kapitel 6 Reguläre (Typ-3-)Sprachen 135
Beispiele für Typ-3-Sprachen 135
Das Wortproblem für Typ-3-Sprachen 136
Aufgaben zu Typ-3-Sprachen 139
Kapitel 7 Kontextfreie (Typ-2-)Sprachen 141
Erste Beispiele 141
Backus-Naur-Form (BNF) 142
Erweiterte Backus-Naur-Form (EBNF) 142
Chomsky-Normalform 144
Die Grenzen kontextfreier Sprachen 146
Ein äquivalentes Maschinenmodell 150
Deterministisch kontextfreie Sprachen 153
Das Wortproblem für kontextfreie Sprachen 154
Abschlusseigenschaften 156
Aufgaben zu kontextfreien Sprachen 157
Kapitel 8 Kontextsensitive und Phasen-Struktur-Sprachen 159
Ein erstes Beispiel 159
Das Wortproblem für Typ-1-Sprachen 160
Das Wortproblem für Typ-0-Sprachen 161
Äquivalente Maschinenmodelle 162
Typ-0-Sprachen 162
Typ-1-Sprachen 164
Teil III Harte Probleme 167
Kapitel 9 Zeitkomplexität von Algorithmen 169
Einführende Überlegungen 169
Zeit- und Speicherkomplexität von Algorithmen 171
Die O-Notation 175
Komplexitätsklassen von Sprachen 177
Aufgaben zur Komplexität von Algorithmen 179
Kapitel 10 Die Kl...