Logo Prof. Dr. Dirk W. Hoffmann
Cover Cover Cover Cover Cover Cover Cover Cover

Hier war der Fehlerteufel am Werk...


Dritte Auflage


175Abb. 4.11: Aus den unteren drei Äquivalenzklassen sind die Wörter 'a', 'aa', 'aaa' zu entfernen.
412Glossareintrag NPSPACE: Im Text steht NSPACE. Es ist NPSPACE gemeint.

Zweite Auflage


47In Definition 2.5 muss es heißen: R0 = { (x,x) | x in M } (im Buch steht R anstatt M)
48In Abb. 2.12 muss die 0 in R0 jeweils hochgestellt sein und nicht tiefgestellt.
49In der Formel oben muss die 0 in R0 hochgestellt sein und nicht tiefgestellt.
632. Absatz: ... in der Lage, ein Tupel (x,y) aus R^2 (hier fehlt die hochgestellte 2 bei R).
69Der Beweis zu Satz 2.4 bedarf mehrerer Korrekturen. Eine korrigierte Version finden Sie hier.
85In der 5. Zeile von oben steht f^M. Gemeint ist f^F.
99In der Formel der ersten und der zweiten Substitution fehlt ganz links eine geöffnete Klammer.
103Im Beweis von (T6) sind zwei Fehler. In der zweiten Beweiszeile fehlt links eine Klammer und in der letzten Zeile ist { A } zu streichen. Im Beweis von (T9) fehlt links zweimal das Symbol '|-'.
168Die Definition für kontextsensitive Grammatiken lässt die Herleitung des leeren Wortes nicht zu. Die folgende Formulierung ist korrekt: "Eine Grammatik heißt kontextsensitiv, wenn jede Produktionsregel l -> r entweder die Beziehung | r | >= | l | erfüllt oder die Form S -> epsilon hat und S in keiner anderen rechten Seite einer Regel vorkommt."
192Im letzten Absatz sind die kontextsensitiven Sprachen gemeint und nicht die kontextfreien.
217Oben: "für jedes Eingabezeichen 'omega'" -> "für jedes Eingabezeichen 'sigma'".
226Mitte: es muss heißen: ", nie jedoch eine Transition mit einer Transition". Im Buch steht Kante anstatt Transition.
230Unten: Der Automat durchläuft die Zustände s_0 bis s_{n+1}.
235Vorletzte Zeile: "Zustand sigma_i" -> Zustand "s_i".
236Der Automat durchläuft die Zustände s_0 bis s_{n+1}.
247Im Automat in der Aufgabe 5.4 ist die mit "b" beschriftete Kante von s1 nach s0 zu viel.
255Der Simulationslauf in Abbildung 6.2 passt nicht zu der Implementierung in Abbildung 6.1. Eine korrigierte Variante finden Sie hier.
262Abb. 6.8 (equal_simulate.while): Es muss heißen: while z < 1 do (in der abgedruckten Version wird 'unequal' implementiert).
272,273Die Indices von xi, ai und bi müssen bei 0 anfangen und nicht bei 1. Entsprechend ist Pi eine n+1-stellige Funktion und keine n-stellige.
274In primrek.loop sind die Zeilen 6 und 7 zu vertauschen.
309Im 2. Absatz von unten muss es heißen: "Für eine entscheidbare Sprache L existiert eine algorithmisch arbeitende Maschine, die ein Element Omega in Sigma-Stern ..." (statt "Omega in L")
313Satz 6.11 ist kein Satz, sondern eine Definition.
351Mitte: Laudau-Symbole => Landau-Symbole.
356Erste Zeile: Laudau-Notationen => Landau-Notationen.
371Die Formel unten lautet korrekt: O(n^k1 + (n^k1)^k2) = O(n^(k1*k2))

Erste Auflage


22,23Der Enigma-Code wurde mit der sogenannten Turing-Bombe gebrochen und nicht mit der (später entwickelten) Colossus.
25Randspalte: Noan Chomsky -> Noam Chomsky.
28Ärgerlicherweise erkennt der abgebildete Primzahltest die Zahl 2 nicht als Primzahl. Eine jetzt (hoffentlich) korrekte Variante finden Sie hier.
43In der Formel zu Abbildung 2.8 ist zusätzlich zu fordern, dass die Mengen M_i nicht die leere Menge sein dürfen.
60Die Funktion pi_3 ist eine Funktion von N^3 nach N und nicht von N^3 nach N^2, wie angegeben.
65P5') Die Behauptung "M = { n | n >= n0 }" ist durch "{ n | n >= n0 } ist Teilmenge von M" zu ersetzen.
67Fünftletzte Zeile: "in Abbildung 2.13" muss heißen: "in Satz 2.13"
67Hinweis: Binärbaume sind in diesem Buch so definiert, dass jeder Knoten entweder 0 oder 2 Söhne hat. Für gewöhnlich wird unter einem Binärbaum aber ein Baum verstanden, in dem jeder Knoten höchstens 2 Söhne hat. Die im Buch als Binärbäume bezeichneten Bäume müssen korrekt als "saturierte Binärbäume" bezeichnet werden.
85Tabelle 3.3 (unten): Das Gleichheitszeichen ist durch das Äquivalenzzeichen zu ersetzen.
118Randspalte: Die Umformungsregeln für die Implikation, die Äquivalenz und die Antivalenz sind falsch. Die korrekte Pränex-Form kann erhalten werden, indem diese Operatoren zunächst in UND, ODER und NICHT aufgelöst werden.
156Tabelle 4.1: In der Ableitungssequenz ist '->' durch '=>' zu ersetzen.
158In den Ableitungssequenzen ist '->' durch '=>' zu ersetzen.
159Randspalte: In der Ableitungssequenz ist '->' durch '=>' zu ersetzen.
161Die angegebene Typ-0-Sprache ist, entgegen dem Gesagten, auch eine Typ-1-Sprache. Eine Typ-1-Grammatik findet sich z.B. in der 1988er Ausgabe des Standardwerks von Hopcroft und Ullman
162Randspalte: Es muss heißen: G = ({S, B, C}, {a,b}, P, S)
163Randspalte: In der Ableitungssequenz ist '->' durch '=>' zu ersetzen.
165Oben: In der Ableitungssequenz ist '->' durch '=>' zu ersetzen.
166Randspalte, letzter Absatz: Es muss heißen: "Um die Wörter der Sprache L_C3..."
167Randspalte: Es muss heißen: L2 := { a^i b^j c^k ..."
169In der Chomsky-Normalform muss auch die Regel S -> epsilon zugelassen werden, wobei S das Startsymbol ist. Ansonsten wäre das leere Wort epsilon nicht ableitbar.
169Randspalte: In den Ableitungssequenzen ist '->' durch '=>' zu ersetzen.
171Randspalte: In den Ableitungssequenzen ist '->' durch '=>' zu ersetzen.
178Randspalte, unteres Bild. Hier fehlt ein Pfeil von C nach S.
181Randspalte: Mit der abgebildeten Grammatik kann das Wort abc nicht erzeugt werden. Eine korrigierte Grammatik finden Sie hier.
183Randspalte: In den Ableitungssequenzen ist '->' durch '=>' zu ersetzen.
187Aufgabe 4.9: In der Grammatik P2 sind die Regeln S->aS, E->aE und Z->aZ zu ergänzen.
189Aufgabe 4.14: Die Grammatik ist durch die korrigierte Grammatik von Seite 181 zu ersetzen.
195In (5.4) ist -> um ein hochgestelltes * zu ergänzen.
197In Tabelle 5.6 sind einige Indizes vertauscht. Die korrigierte Tabelle finden Sie hier.
200In (5.12) ist -> um ein hochgestelltes * zu ergänzen.
202Die korrekte Bezeichnung des Zustands s1s2s3s4 in Abb. 5.10 ist s0s1s2s3.
205In Gleichung (5.28) sind die Mengenklammern zu entfernen. Epsilon-Hüllen sind bereits Mengen.
212In der Definition des Kellerautomaten fehlt der Zusatz, dass die Zustandsübergangsfunktion immer nur auf endliche Mengen abbilden darf.
249Dritter Absatz: Es wird zweimal von der Menge $T$ gesprochen. Gemeint ist die Menge T_i.
257In Definition 6.7 muss es heißen: h : N_0^3 -> N_0 und nicht h : N_0 -> N_0^3.
277Zeile 6: von "s_i nach e_i" muss korrekt heißen: "von e_i nach s_i".
282Dritte Zeile: "besitzt vier Zustände". Tatsächlich sind es nur drei Zustände.
293Vorletzter Absatz: "Beachten Sie, dass die Indizes der Zeichen in \nu aufsteigend und in \omega absteigend notiert sind.". Hier sind aufsteigend und absteigend zu vertauschen.
311fIn der Bildunterschrift und im Fließtext heißt es: "wird ein direkter Zusammenhang zwischen der untersuchten Maschineneigenschaft E und der Terminierung von H hergestellt". Hier ist H durch T zu ersetzen.
316Randspalte: In der PCP-Instanz fehlt die Regel (0 < 1 < 1 < , < 1 < 0 < 0).
316In der Abbildungsunterschrift ist PKP durch PCP und MPKP durch MPCP zu ersetzen.
3165. Zeile von unten: i != 0 muss i_1 != 0 lauten.
331In Definition 7.1 muss es "a_i v_i" heißen (und nicht "a_i v_1" wie abgedruckt).
340Definition 7.5, letzte Zeile: A ist durch a zu ersetzen.
343"Definition 7.6" ist ein Satz und muss korrekterweise "Satz 7.6" heißen.
357Formel (7.21) lautet korrekt: O(n^k1 + (n^k1)^k2) = O(n^(k1*k2))