Logo
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))