訂正のページ：
本書の誤りについて報告します． 新しく気が付いた間違いの順に並べてあります．

Updated 11/15/02.

以下の間違いは，第２刷では訂正されています．

★重要な間違い★

4. p.138, 問 1.9 の解答例プログラム A.1（指摘者 T. Watanabe, 2/3/02）

（誤っている点）

   program match (string t, p)
       char a[..], b[..];
       i <- 1; j <- 1;
       a <- str_to_char(x); b <- str_to_char(y);
       while (true) {
           if (b[j] = 列終端) { return(true); }
           if (a[i] = 列終端) { return(false); }
           if (a[i] = b[j]) {
               i <- i + 1;
               j <- j + 1;
           }
           else {
               i <- i + 1;         /* ここが誤り? */
               j <- 1;
           }
       }
   program end.

（訂正）

   program match (string t, p)
       char a[..], b[..];
       i <- 1; j <- 1;
       a <- str_to_char(x); b <- str_to_char(y);
       while (true) {
           if (b[j] = 列終端) { return(true); }
           if (a[i] = 列終端) { return(false); }
           if (a[i] = b[j]) {
               i <- i + 1;
               j <- j + 1;
           }
           else {
               i <- i - j + 2;      /* パターンを1つずらす */
               j <- 1;
           }
       }
   program end.

3. p.139, 問 1.15 の解答例プログラム A.4（指摘者 T. Nagai, 1/11/02）

（誤っている点と訂正）

1: if($1 >= $2) goto 3 は間違い．
1: if($1 < $2) goto 3 が正しい．

2. p.47 定理 2.1 補足（指摘者 S. Chiba，11/21/01）

（誤っている点と訂正）
gcd(x,0) = gcd(0,x) = 0 と定義しているが，間違い． gcd(x,0) = gcd(0,x) = x が正しい．

1. p.85 例題 3.1（指摘者 K. Kobayashi，10/3/01）

（誤っている点）
ここに説明されているのは，ポストの対応問題ではない．この問題自体 は，簡単に解くことができる．

（訂正）

与えられた文字列の組 P = { (s1,t1), (s2,t2), ..., (sn,tn) }
に対し，その中から適当な組を選び（2 度以上選ぶことも可）
並べることで，まったく同じ文字列の組を作ることができるかど
うかを判定せよ．

例も同様に訂正．たとえば，

   P = { (aba, abaab), (aba, a), (bba, bbaa), (aab, abaab) }

だと，

  (aba, abaab), (aba, a), (bba, bbaa), (aab, abab), (aba, a)

と選べば，各組の左だけで，

  s = aba aba bba aab aba

ができ，右だけでも

  t = abaab a bbaa abab a

となるため等しい列ができる．したがって，P に対しては，ポス
トの対応問題は Yes である．

☆軽微な間違い☆

3. p.28 の 7 行目（指摘者匿名，1/31/02）

（誤っている点と訂正）
飛ぶ（ジャンプ）することが → 飛ぶ（ジャンプする）ことが

2. p.21 の 7 行目（指摘者匿名，1/31/02）

（誤っている点と訂正）
終了する考える → 終了すると考える

1. p.134, p.135 参考文献の番号（指摘者 K. Kobayashi，10/3/01）

（誤っている点と訂正）
量子計算に触れている文献は [4] ではなく [3]． Ｃ言語の文献の説明では，[5] と [6] が逆．