Inhaltsverzeichnis	8
	Vorwort	12
	Teil I: Berechenbarkeit	14
	Kapitel 1: Abstrakte Rechnermodelle	18
	1.1 Registermaschinen	19
	1.2 Turingmaschinen	37
	1.2.1 Deterministische Turingmaschinen	37
	1.2.2 Turing-Berechenbarkeit	45
	1.2.3 Mehrband-Turingmaschinen	50
	1.2.4 Kostenmaße für DTMs	57
	1.2.5 Turingmaschinen mit linksseitig beschränktem Band	59
	1.2.6 »Programmierung« von DTMs	61
	1.3 Äquivalenz der Berechenbarkeitsbegriffe	64
	1.3.1 Simulation von Registermaschinen durch Turingmaschinen	65
	1.3.2 Simulation von Turingmaschinen durch Registermaschinen	69
	1.3.3 Churchsche These	76
	1.4 Übungen	78
	Kapitel 2: Entscheidungsprobleme	86
	2.1 Entscheidbarbeit und Semientscheidbarkeit	89
	2.2 Das Halteproblem	100
	2.3 Nichtdeterminismus	117
	2.4 Übungen	127
	Teil II: Komplexität	132
	Kapitel 3: Komplexitätsklassen	138
	3.1 Zeitkomplexität	138
	3.2 Platzkomplexität	146
	3.3 Übungen	150
	Kapitel 4: Das P-NP-Problem	152
	4.1 NP-Vollständigkeit	152
	4.2 Der Satz von Cook	156
	4.2.1 Die NP-Vollständigkeit von SAT	156
	4.3 Weitere NP-vollständige Probleme	163
	4.3.1 3SAT	165
	4.3.2 Das Cliquenproblem	168
	4.3.3 Das Rucksackproblem	171
	4.3.4 0/1 Integer Linear Programming	176
	4.4 Die Klasse coNP	179
	4.5 PSPACE-Vollständigkeit	183
	4.6 Übungen	188
	Teil III: Formale Sprachen	194
	Kapitel 5: Grammatiken	196
	5.1 Die Chomsky-Hierarchie	197
	5.2 Sprachen vom Typ 0	211
	5.3 Kontextsensitive Sprachen	212
	5.4 Das Wortproblem für Sprachen vom Typ 0 und vom Typ 1	216
	5.5 Übungen	219
	Kapitel 6: Reguläre Sprachen	222
	6.1 Endliche Automaten	222
	6.1.1 Deterministische endliche Automaten	223
	6.1.2 Nichtdeterministische endliche Automaten	228
	6.2 Eigenschaften regulärer Sprachen	237
	6.2.1 Konstruktion endlicher Automaten	237
	6.2.2 Algorithmen für den Nachweis von Eigenschaften regulärer Sprachen	247
	6.2.3 Das Pumping Lemma für reguläre Sprachen	250
	6.3 Reguläre Ausdrücke	253
	6.4 Minimierung von endlichen Automaten	261
	6.4.1 Der Satz von Myhill & Nerode	261
	6.4.2 Der Minimierungsalgorithmus	268
	6.5 Übungen	273
	Kapitel 7: Kontextfreie Sprachen	278
	7.1 Grundbegriffe	278
	7.2 Die Chomsky-Normalform	284
	7.3 Der Cocke-Younger-Kasami-Algorithmus	290
	7.4 Eigenschaften kontextfreier Sprachen	293
	7.4.1 Das Pumping Lemma für kontextfreie Sprachen	293
	7.4.2 Abschlusseigenschaften kontextfreier Sprachen	296
	7.5 Die Greibach-Normalform	297
	7.6 Kellerautomaten	300
	7.7 Übungen	313
	Kapitel 8: Deterministisch kontextfreie Sprachen	318
	8.1 Deterministische Kellerautomaten	319
	8.2 LR(0)-Grammatiken	325
	8.2.1 Die LR(0)-Bedingung	326
	8.2.2 Ein nichtdeterministischer LR(0)-Parser	337
	8.2.3 LR(0)-Items	341
	8.2.4 Berechnung der Itemmengen	350
	8.2.5 DKAs für LR(0)-Grammatiken	360
	8.3 LR(k)-Grammatiken	368
	8.3.1 Die LR(k)-Bedingung	368
	8.3.2 LR(k)-Items	371
	8.3.3 Die Parsetabellen	375
	8.3.4 Der LR(k)-Parser	379
	8.4 Übungen	381
	Kapitel 9: Entscheidungsprobleme für formale Sprachen	382
	9.1 Das Postsche Korrespondenzproblem	383
	9.2 Unentscheidungsergebnisse für formale Sprachen	393
	9.2.1 Unentscheidbarkeitsergebnisse für deterministisch kontextfreie Sprachen	394
	9.2.2 Unentscheidbarkeitsergebnisse für kontextfreie Sprachen	398
	9.2.3 Unentscheidbarkeitsergebnisse für kontextsensitive Sprachen	400
	9.3 »Schwierige« Probleme für reguläre Sprachen	401
	9.4 Übungen	404
	Kapitel 10: Zusammenfassung	406
	Anhang A: Die Güte von Algorithmen	408
	Anhang B: Aussagenlogik	410
	Anhang C: Formale Sprachen	414
	Literaturverzeichnis	416
	Register	420