# 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.

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