Dirk W. Hoffmann |
Theoretische Informatik |
5. Auflage, 2022 |
Carl Hanser Verlag |
ISBN 978-3446470293 |
Hier war der Fehlerteufel am Werk...
4. Auflage
- Seite 187
2. Zeile von oben: Es muss heißen "1 ≤ k < n", nicht "1 ≤ k ≤ n".
3. Auflage
- Seite 175
Abb. 4.11: Aus den unteren drei Äquivalenzklassen sind die Wörter 'a', 'aa', 'aaa' zu entfernen.
- Seite 185
Unten (Ogdens Lemma): Die Argumentation deckt nicht alle möglichen Fälle an. Eine Korrektur finden Sie hier.
- Seite 412
Glossareintrag NPSPACE: Im Text steht NSPACE. Es ist NPSPACE gemeint.
- Seite 291
In 6.38 sind ein paar Indizes falsch. Eine korrigierte Abbildung finden Sie hier.
2. Auflage
- Seite 47
In Definition 2.5 muss es heißen: R0 = { (x,x) | x in M } (im Buch steht R anstatt M)
- Seite 48
In Abb. 2.12 muss die 0 in R0 jeweils hochgestellt sein und nicht tiefgestellt.
- Seite 49
In der Formel oben muss die 0 in R0 hochgestellt sein und nicht tiefgestellt.
- Seite 63
2. Absatz: ... in der Lage, ein Tupel (x,y) aus R^2 (hier fehlt die hochgestellte 2 bei R).
- Seite 69
Der Beweis zu Satz 2.4 bedarf mehrerer Korrekturen. Eine korrigierte Version finden Sie
hier.
- Seite 85
In der 5. Zeile von oben steht f^M. Gemeint ist f^F.
- Seite 99
In der Formel der ersten und der zweiten Substitution fehlt ganz links eine geöffnete Klammer.
- Seite 103
Im 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 '|-'.
- Seite 168
Die 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."
- Seite 192
Im letzten Absatz sind die kontextsensitiven Sprachen gemeint und nicht die kontextfreien.
- Seite 217
Oben: "für jedes Eingabezeichen 'omega'" -> "für jedes Eingabezeichen 'sigma'".
- Seite 226
Mitte: es muss heißen: ", nie jedoch eine Transition mit einer Transition". Im Buch steht Kante anstatt Transition.
- Seite 230
Unten: Der Automat durchläuft die Zustände s_0 bis s_{n+1}.
- Seite 235
Vorletzte Zeile: "Zustand sigma_i" -> Zustand "s_i".
- Seite 236
Der Automat durchläuft die Zustände s_0 bis s_{n+1}.
- Seite 247
Im Automat in der Aufgabe 5.4 ist die mit "b" beschriftete Kante von s1 nach s0 zu viel.
- Seite 255
Der Simulationslauf in Abbildung 6.2 passt nicht zu der Implementierung in Abbildung 6.1. Eine korrigierte Variante finden Sie hier.
- Seite 262
Abb. 6.8 (equal_simulate.while): Es muss heißen: while z < 1 do (in der abgedruckten Version wird 'unequal' implementiert).
- Seite 272 und 273
Die 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.
- Seite 274
In primrek.loop sind die Zeilen 6 und 7 zu vertauschen.
- Seite 309
Im 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")
- Seite 313
Satz 6.11 ist kein Satz, sondern eine Definition.
- Seite 351
Mitte: Laudau-Symbole => Landau-Symbole.
- Seite 356
Erste Zeile: Laudau-Notationen => Landau-Notationen.
- Seite 371
Die Formel unten lautet korrekt: O(n^k1 + (n^k1)^k2) = O(n^(k1*k2))
1. Auflage
- Seite 22 und 23
Der Enigma-Code wurde mit der sogenannten Turing-Bombe gebrochen und nicht mit der (später entwickelten) Colossus.
- Seite 25
Randspalte: Noan Chomsky -> Noam Chomsky.
- Seite 28
Ärgerlicherweise erkennt der abgebildete Primzahltest die Zahl 2 nicht als Primzahl. Eine jetzt (hoffentlich) korrekte Variante finden Sie hier.
- Seite 43
In der Formel zu Abbildung 2.8 ist zusätzlich zu fordern, dass die Mengen M_i nicht die leere Menge sein dürfen.
- Seite 60
Die Funktion pi_3 ist eine Funktion von N^3 nach N und nicht von N^3 nach N^2, wie angegeben.
- Seite 65
P5') Die Behauptung "M = { n | n >= n0 }" ist durch "{ n | n >= n0 } ist Teilmenge von M" zu ersetzen.
- Seite 67
Fünftletzte Zeile: "in Abbildung 2.13" muss heißen: "in Satz 2.13"
- Seite 67
Hinweis: 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.
- Seite 85
Tabelle 3.3 (unten): Das Gleichheitszeichen ist durch das Äquivalenzzeichen zu ersetzen.
- Seite 118
Randspalte: 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.
- Seite 156
Tabelle 4.1: In der Ableitungssequenz ist '->' durch '=>' zu ersetzen.
- Seite 158
In den Ableitungssequenzen ist '->' durch '=>' zu ersetzen.
- Seite 159
Randspalte: In der Ableitungssequenz ist '->' durch '=>' zu ersetzen.
- Seite 161
Die 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
- Seite 162
Randspalte: Es muss heißen: G = ({S, B, C}, {a,b}, P, S)
- Seite 163
Randspalte: In der Ableitungssequenz ist '->' durch '=>' zu ersetzen.
- Seite 165
Oben: In der Ableitungssequenz ist '->' durch '=>' zu ersetzen.
- Seite 166
Randspalte, letzter Absatz: Es muss heißen: "Um die Wörter der Sprache L_C3..."
- Seite 167
Randspalte: Es muss heißen: L2 := { a^i b^j c^k ..."
- Seite 169
In 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.
- Seite 169
Randspalte: In den Ableitungssequenzen ist '->' durch '=>' zu ersetzen.
- Seite 171
Randspalte: In den Ableitungssequenzen ist '->' durch '=>' zu ersetzen.
- Seite 178
Randspalte, unteres Bild. Hier fehlt ein Pfeil von C nach S.
- Seite 181
Randspalte: Mit der abgebildeten Grammatik kann das Wort abc nicht erzeugt werden. Eine korrigierte Grammatik finden Sie hier.
- Seite 183
Randspalte: In den Ableitungssequenzen ist '->' durch '=>' zu ersetzen.
- Seite 187
Randspalte: Mit der abgebildeten Grammatik kann das Wort abc nicht erzeugt werden. Eine korrigierte Grammatik finden Sie hier.
- Seite 189
Aufgabe 4.14: Die Grammatik ist durch die korrigierte Grammatik von Seite 181 zu ersetzen.
- Seite 195
In (5.4) ist -> um ein hochgestelltes * zu ergänzen.
- Seite 197
In Tabelle 5.6 sind einige Indizes vertauscht. Die korrigierte Tabelle finden Sie hier.
- Seite 200
In (5.12) ist -> um ein hochgestelltes * zu ergänzen.
- Seite 202
Die korrekte Bezeichnung des Zustands s1s2s3s4 in Abb. 5.10 ist s0s1s2s3.
- Seite 205
In Gleichung (5.28) sind die Mengenklammern zu entfernen. Epsilon-Hüllen sind bereits Mengen.
- Seite 212
In der Definition des Kellerautomaten fehlt der Zusatz, dass die Zustandsübergangsfunktion immer nur auf endliche Mengen abbilden darf.
- Seite 249
Dritter Absatz: Es wird zweimal von der Menge $T$ gesprochen. Gemeint ist die Menge T_i.
- Seite 257
In Definition 6.7 muss es heißen: h : N_0^3 -> N_0 und nicht h : N_0 -> N_0^3.
- Seite 277
Zeile 6: von "s_i nach e_i" muss korrekt heißen: "von e_i nach s_i".
- Seite 282
Dritte Zeile: "besitzt vier Zustände". Tatsächlich sind es nur drei Zustände.
- Seite 293
Vorletzter Absatz: "Beachten Sie, dass die Indizes der Zeichen in \nu aufsteigend und in \omega absteigend notiert sind.". Hier sind aufsteigend und absteigend zu vertauschen.
- Seite 311f
In 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.
- Seite 316
Randspalte: In der PCP-Instanz fehlt die Regel (0 < 1 < 1 < , < 1 < 0 < 0).
- Seite 316
Randspalte: In der PCP-Instanz fehlt die Regel (0 < 1 < 1 < , < 1 < 0 < 0).
- Seite 316
Randspalte: In der PCP-Instanz fehlt die Regel (0 < 1 < 1 < , < 1 < 0 < 0).
- Seite 316
In der Abbildungsunterschrift ist PKP durch PCP und MPKP durch MPCP zu ersetzen.
- Seite 316
5. Zeile von unten: i != 0 muss i_1 != 0 lauten.
- Seite 331
In Definition 7.1 muss es "a_i v_i" heißen (und nicht "a_i v_1" wie abgedruckt).
- Seite 340
Definition 7.5, letzte Zeile: A ist durch a zu ersetzen.
- Seite 343
"Definition 7.6" ist ein Satz und muss korrekterweise "Satz 7.6" heißen.
- Seite 357
Formel (7.21) lautet korrekt: O(n^k1 + (n^k1)^k2) = O(n^(k1*k2))