- Pages xii, 14, 59, 79, 105, 110, 124, and 154:
- The reference [Rey81] (J. C. Reynolds, The Craft of Programming, Prentice-Hall International) is out of print;
however, it is available here.
- Page 42, 2nd paragraph:
- Two occurrences of
-
- n>1 implies n-1 > 1
should be
-
- n>1 implies n-1 > 0
Also, one occurrence of
-
- n>0 implies n >= 0
should be
-
- n>0 implies n >= 1
and the last line of the formal proof should be
-
- n>1 {n = n-1;} n>=1
(Thanks to Larry Marable and Kim Ho.)
- Page 76, Exercise 3.24:
- The test in the loop body
should be x < A[mid].
- Page 91, line 9:
- The pre-condition for sorting should be 0 <= n <= max.
- Page 96, added conditions:
- The second condition should be Exists(k=m, k<j) A[k] <= x.
(Thanks to Ryan Kavanagh.)
- Page 200, line 4:
- This should read "If \(S\)
and \(T\)
are regular languages over the same vocabulary \(\Sigma\), ...".
- Page 203, Exercise 9.11:
- In the books24x7 (on-line) version, the (b) and (c) parts should be
\(\{\,\verb\0\^i \verb\1\^j\mid \mbox{for all }i,j\geq 0\,\}\)
and
\(\{\,\verb\0\^i \verb\1\^j\mid \mbox{for all }i>j\geq 0\,\}\), respectively.
- Page 238, Section 11.3.5:
- An additional condition for recursive-descent parsing is that it must not be possible
to derive the empty
string \(\varepsilon\)
using more than
one of the
productions for any non-terminal
\(\langle N \rangle\). On the other hand,
when the empty string is derived using
the \(i\)'th production
\(\langle N \rangle ::= \alpha_i\)
it is possible to weaken the second requirement
stated in the text by allowing overlap between
\(\textit{follow} \langle N \rangle\)
and
\(\textit{first}(\alpha_i)\).
A corrected version of pages 238-39 may be found
here.
- Page 283, Solution to Exercise 7.8 (a):
- The use of | for union may be confusing; the following should be
clearer:
$$\begin{array}{lcl}
rhs &=& {\verb\1\+ \verb\0\ L + L \verb\0\}\\
&=&
\verb\1\
+ \verb\0\\{\,\verb\0\^i\verb\1\\verb\0\^j\mid i,j\geq 0\,\}
+ \{\,\verb\0\^i\verb\1\\verb\0\^j\mid i,j\geq 0\,\}\verb\0\
\\
&=&
\{\,\verb\0\^i\verb\1\\verb\0\^j\mid i=j= 0\,\}
+ \{\,\verb\0\^i\verb\1\\verb\0\^j\mid i>0, j\geq 0\,\}
+ \{\,\verb\0\^i\verb\1\\verb\0\^j\mid i\geq 0, j>0\,\}
\\
&=&
\{\,\verb\0\^i\verb\1\\verb\0\^j\mid i\geq 0, j\geq 0\,\}
\\
&=& L
\\
&=& lhs
\end{array}$$
- Page 34, line -10:
- "seach" should be "search".
- Page 220, line 13:
- "recognized" should be "generated".
(Thanks to Kai Salomaa.)
Last modified October 5, 2011.