Banner

Hier war der Fehlerteufel am Werk...

Zweite Auflage

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).
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 '|-'.
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.
250Abb. 6.8 (equal_simulate.while): Es muss heißen: while z < 1 do (in der abgedruckten Version wird 'unequal' implementiert).
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))