×

Introduction to automata theory, languages and computation. 3., korr. Aufl., 1., korr. Nachdr. (Einführung in die Automatentheorie, formale Sprachen und Komplexitätstheorie.) (German) Zbl 0847.68065

Bonn: Addison-Wesley. ix, 461 p. (1996).
Seit 1979 ist dieser “Klassiker”, der die wesentlichen Gebiete der Theoretischen Informatik durchstreift, auf dem Markt.
Es werden nach einer allgemeinen Einführung zur mengentheoretischen Notation, zu Graphen und Induktionsbeweisen, etc. zunächst die Eigenschaften der endlichen Automaten, regulären Ausdrücke und regulären Grammatiken behandelt. Die kontextfreien Spachen mit entsprechenden Normalformen und Kellerautomaten sind das nächste Thema. Über die Turingmaschine wird dann der Berechenbarkeitsbegriff eingeführt und schließlich verschiedene Unentscheidbarkeitsergebnisse präsentiert, wobei – etwas ungewöhnlich – über die Charakterisierung gültiger/ungültiger Turingmaschinen-Berechnungen viele Unentscheidbarkeitsergebnisse in den Formalen Sprachen auf eine einheitliche Weise geführt werden können. Die Behandlung der deterministisch kontextfreien Sprachen führt nahtlos an Probleme des Übersetzerbaus heran. Etwas ungewöhnlich und nicht mehr ganz “zeitgemäß” ist das 11. Kapitel, das sich mit abstrakten Sprachenfamilien (AFL’s) auseinandersetzt. Die Komplexitätstheorie wird in recht traditioneller Weise, einschließlich eines Ausflugs in die abstrakte Komplexitätstheorie, abgehandelt. Das (letzte) Kapitel 14 stellt schließlich schlaglichtartig einige zuvor nicht behandelte Themen zusammen, wie Hilfskellerautomaten, Lindenmayersysteme und indizierte Sprachen.
Die erste deutsche Übersetzung des Werkes muß leider als grauenhaft bezeichnet werden. Durch die Übersetzung waren viele Beweise und Formulierungen nicht mehr verstehbar oder doppeldeutig. Zum Beispiel wurde “for any \(\varepsilon> 0\) holds…” durchweg mit “für ein \(\varepsilon> 0\) gilt…” übersetzt, was ganz sicher nicht dieselbe Bedeutung hat. Im vorliegenden korrigierten Nachdruck sind diese Übersetzungsfehler – soweit dies übersehbar ist – ausgemerzt.
Das amerikanische Original, und inzwischen auch die deutsche Übersetzung, ist ein absolut empfehlenswertes Buch. Die Teile des Buches, die sich mit “klassischen” Themen beschäftigen, sind kaum in anderen Büchern verständlicher und lesbarer dargestellt. Die Auswahl der Themen war zu der Zeit, als das Buch erstmalig erschien, durchaus wegweisend.
Heutzutage würde man aber die Teile, die sich mit der Komplexitätstheorie und algorithmischen Aspekten befassen, sicher anders – moderner – schreiben. Einige neue wesentliche Resultate sollten heutzutage mit einbezogen werden, wie der Komplementabschluß der nichtdeterministischen Bandklassen, sowie interaktive Beweissysteme, u.a. Umgekehrt sollte anderer “Balast” heutzutage weggelassen werden. Trotzdem: alles in allem ein sehr empfehlenswertes Buch.
Reviewer: U.Schöning (Ulm)

MSC:

68Q45 Formal languages and automata
68-01 Introductory exposition (textbooks, tutorial papers, etc.) pertaining to computer science
03D10 Turing machines and related notions
03D15 Complexity of computation (including implicit computational complexity)
03D35 Undecidability and degrees of sets of sentences
68Q15 Complexity classes (hierarchies, relations among complexity classes, etc.)

Citations:

Zbl 0426.68001
PDF BibTeX XML Cite