Red Errata for the 1st and 2nd Printings (as of 5/25/2001)

Chapter 2

• Page 30, Figure 2.6: Perl's \w matches any alphanumeric or an underscore not a space. So replace the space symbol with an underscore.

Chapter 5

• Page 156, Figure 5.5: There are two major changes to this code: (1) we need to initialize all of the 0th row and column to their respective indexes as in Figure 5.6, and (2) the two main loops should start at 1 not 0. We'll have a replacement page for this soon.
• Page 157, Figure 5.6: There are five errors in this table: entry [1,4] 5 should be a 3; entry [6,3] 9 should be a 7; entry [7,1] 8 should be a 6; entry [9,2] 11 should be 9; and entry[9,5] 12 should be 10.
• Page 176, Figure 5.16: , The line in the inner loop doesn't perform the required sum. It should read:

forward[s',t+1] <-- forward[s',t+1] + forward[s,t]*a[s,s']*b[s',o_t]

Chapter 6

• Page 210, Figure 6.8: A number of the counts in this table are off. Here are the correct entries.

	I	want	to	eat	Chinese	food	lunch
I	6.12	740	0.680	9.52	0.680	0.680	0.680
want	1.71	0.429	338	0.429	3.09	3.86	3.00
to	2.67	0.668	7.35	575	2.67	0.668	8.69
eat	0.367	0.367	1.10	0.367	7.35	1.10	19.5
Chinese	0.349	0.116	0.116	0.116	0.116	14.1	0.233
food	9.64	0.482	8.68	0.482	0.482	0.482	0.482
lunch	1.11	0.221	0.221	0.221	0.221	0.442	0.221

• Page 212, Equation 6.23: Replace each of the 5 w_{i-1} with a w_{x}.
• Page 212, Equation 6.24: Remove the summation and add an "if (c_{w_{x}w_{i}} > 0)" to the right side of the equation.
• Page 218, Equation 6.35: Change the right side denominator from "c(w_{1}^{n-N+1})" to "c(w_{n-N+1}^{n-1})".
• Page 219, Equation 6.37: To make the normalization of beta explicit, replace the existing equation with the following:

  \begin{eqnarray}
  \alpha(w_{n-N+1}^{n-1}) &=&\frac
  {\beta(w_{n-N+1}^{n-1})}
  {\sum_{w_{n}:c(w_{n-N+1}^{n})=0}P{(w_{n}|w_{n-N+2}^{n-1})}}\nonumber\\
  &=&\frac
  {1 - \sum_{w_{n}:c(w_{n-N+1}^{n})>0}\tilde{P}{(w_{n}|w_{n-N+1}^{n-1})}}
  {1 - \sum_{w_{n}:c(w_{n-N+1}^{n})>0}\tilde{P}{(w_{n}|w_{n-N+2}^{n-1})}}
  \end{eqnarray}
  

• Page 219, line 11: Change the "m-1" superscript of c to "n-1".
• Page 219, unnumbered equation at bottom of page: Replace the "n"s with "i"s in the superscripted and subscripted arguments to alpha.
• Page 226, Equation 6.49: Both expressions are missing minus signs. They should read lim - 1/n.
• Page 227, Equation 6.51: Missing the same minus sign as 6.49.

Chapter 7

• Page 256, Figure 7.14: The main loop is missing from this pseudocode. Add a "While(queue is not empty)" after the initialization of the queue and before the Pop.

Chapter 10

• Page 366, Figure 10.6: In the following, assume that line numbering starts with the assignment of agenda as line 1.
• The "CAT" function on line 7 returns the grammatical category of a node in a parse tree. So this line is checking to see if the grammatical category of the current node to be expanded in this search state is a part-of-speech category.
• The "if" on line 8 should be similar to the one on line 7, ie. CAT(NODE-TO-EXPAND(current-search-state))
• The "subset" symbol on line 9 should be an "in" instead".
• Remove the "else return reject" on lines 12 and 13; it causes a premature termination of the search.
• The call to NEXT on line 19 should be a POP since this algorithm is explicitly depth-first.
• Page 381, Figure 10.16, ENQUEUE definition: The use of PUSH here is a little unclear. The newly added states need to go at the end of the chart-entry, not the front, to ensure that they get processed. If that matches your intuitions for PUSH (Perl and Python hackers for example) then leave it as is. If you're a Lisper then you can go with PushEnd or Append.
• Page 384, Figure 10.17: The order of the states in this chart doesn't reflect the order in which the algorithm would enter them. Chart[0] should look like the following:

Gamma -> · S

S -> · NP VP

S -> · Aux NP VP

S -> · VP

NP -> · Det NOMINAL

NP -> · Proper-Noun

VP -> · Verb

VP -> · Verb NP

• Page 390, Figure 10.21: Various arcs are messed up: Delete both arcs between states 9 and 3; add an epsilon transition from state 9 to state 4, and another from state 9 to state 3.

Chapter 12

• Page 455, Figure 12.3: The probabilistic CYK algorithm in this figure is flawed in a number of ways. See the replacement page for a correct version.

Chapter 17

• Page 650, line 10: The equation for computing the length of a vector is missing a square root. It should be:

Sqrt(Sum (w_i **2)).
• Page 650, Matrix A: This matrix is transposed. It should look like

.41	.98	0
.81	0	.98
.41	.16	.19