Errors and Corrections

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.