## Prentice Hall Edition (2009)

Errata for the first and second printings of the 2nd Edition of Speech and Language Processing. Critical items are in red.

### Chapter 1

• Page 4, bottom: The "duck" example explanation is backwards (and confusing). In Examples (1.5) and (1.8) "her duck" evokes distinct entities, while in Example (1.6) only one entity is evoked.
• Page 10, middle: Zelig Harris should be Zellig Harris.

### Chapter 2

• Pages 28 and 33: In the transition tables the "0" indicates that there is no transition for that entry. It does not refer to some "0" in the alphabet.
• Page 35, Figure 2.19: The function NEXT returns an element from the agenda and removes it (i.e, it does a pop in the case of a stack).

### Chapter 4

• Page 105, Equation 4.36: Replace with the following (only the third line changes):
• Page 108, Equation 4.46 (repeated from 4.36): Replace with
• Page 122, Exercise 4.9: The allusion to Viterbi in this exercise implies that there is a polynomial time solution to this problem when in fact it is NP-hard. The following re-wording should help.

(Advanced) Suppose someone took all the words in a sentence and reordered
them randomly.  Write a program that takes as input such a bag of words and
produces as output a guess at the original order. You will need to  use an N-gram
grammar produced by your N-gram program (on some corpus). This problem is NP-hard
so you will want to think of an approximate solution rather than an exact solution.
Applying beam-search and other advanced search techniques used for machine translation
search, introduced in Chapter 24, will be handy. This task is sometimes called
bag generation.
s

### Chapter 6

• Page 179, the first sentence of section 6.3: The reference to Figure 6.2b should be to Figure 6.3
• Page 182, Figure 6.7: The computation for \alpha_2(2) should read \alpha_2(2)=.32*.14+.02*.08=.0464.
• Page 186, Equations 6.24, 6.25, and 6.28: These should end with $a_{iF}$, not $a_{i,F}$, to be consistent with the other formulas in the section.
• Page 186, Equation 6.24: $v_t(q_F)$ should be replaced by $v_T(q_F)$ (i.e., the correct equation should use capital T not t).
• Page 188, Equation 6.30: $\beta_1(0)$ should be replaced with $\beta_1(q_0)$ (for consistency with pages 145 and 175).
• Page 190, Equation 6.36: $\beta_T(1)$ should be replaced with $\beta_1(q_0)$ and $\alpha_T(N)$ should be replaced by $\alpha_T(q_F)$, as follows:
• Page 190, Equation 6.37: The denominator should be replaced by $\alpha_T(q_F)$ as follows:
• Page 190, Equation 6.38: The variable j is incorrectly overloaded, replace with the following:
• Page 192, Figure 6.16: the denominators of the two E-step equations are inconsistent and the denominator of the first M-step equation overloads the variable j. Replace the E-step and first part of M-step with the following:

### Chapter 8

• Page 281: "mean/beat" should be "meat/beat"

### Chapter 9

• Pages 308-312, text and Equations 9.29, 9.30, 9.35, 9.36, 9.39, 9.40, 9.41, 9.42: In these 4 pages we inadvertently used ξt(i) instead of γt(i) to refer to the probability of being in state i at time t. The use of ξ is confusing since in Chapter 6 we used γ for this probability and ξ for something else. Although this chapter is internally consistent in its use of ξ, for compatibility with Chapter 6 we recommend that lecturers and readers replace all the instances of ξ in these 4 pages with γ
• Page 312, Equation 9.39: The summation should be from 1 to N, rather than the N being a multiplicand.
• Page 315, last paragraph: N/|V| should be |V|-N

### Chapter 11

• Page 365, the second table under "Shortening": s:ap should be sa:p

### Chapter 13

• Page 428, Figure 13.1: In the first entry of the Lexicon add the word "the" as a possible expansion of the nonterminal "Det".
• Page 439, Figure 13.9: Add an X2 constituent to the [0,5] entry.
• Page 442, Figure 13.12: Ditto.
• Page 441, Figure 13.11: Upper right index should be [0,n].
• Page 455, Equation 13.14: The denominator is missing the addition symbols, the correct equation is
• Page 455, Equation 13.15: the denominator on the left has the weights in the wrong place, the correct equation is

### Chapter 14

• Page 479, Equation 14.36: The denominator is missing the addition symbols, the correct equation is
• Page 480, Equation 14.37: the denominator on the left has the weights in the wrong place, the correct equation is

### Chapter 16

• Page 544, Exercises 16.3 and 16.4: x∈ a,b* should be x ∈ {a,b}*
• Page 544, Exercises 16.3 and 16.4: xR should be defined as the reverse of the string x.

### Chapter 17

• Page 567, middle: In the FOL formulae, EndPoint(i,e) should be EndPoint(i,n), Precedes(e, Now) should be Precedes(n, Now), and EndPoint(e,n) should be EndPoint(i,n). And the quantified variable t in these FOL is extraneous.

### Chapter 18

• Page 588, Equation 18.14: Sem should be lowercase in semantic attachment.
• Page 589, Equation 18.19: CFG rule should be Verbclosed to match the example.
• Page 590, second FOL expression: ClosedThing(Maharani) should be ClosedThing(e,Maharani).
• Page 595, Figure 18.6: The store for the NP is missing an opening bracket.
• Page 596, paragraph -2, last sentence: Second h1 should be h2. That is, h2 stands for the nuclear scope of the menu.

### Chapter 20

• Page 657, Figure 20.8: simjc should be simJC
• Page 670, middle of last paragraph before 20.9: "Recall from Section 20.10" should be "As we'll see in Section 20.10"
• Page 673, line 2: VP →NP PP should be VP →VBD NP PP
• Page 675, line -1: "usuing" should be "using"

### Chapter 21

• Page 685: The reference to sentence (21.8ab) should just refer to sentence (21.8)
• Page 685: The words "cohesion!chain" should be "cohesion chain"

### Chapter 22

• Page 741, Equation 22.17: Replace with the following
• Page 744, TimeML example: The final tag should be </TIMEX3>, not </TIMEX2>.
• Page 747, Figure 22.22: Change "YYYY-nnW" to "YYYY-Wnn" and change "2007-27W" to "2007-W27".
• Page 764, Problem 22.11: The phrase your corpus here refers to a previous problem that didn't make the final cut. Here's the missing text.

Develop a new template that covers a situation commonly reported
on by standard news sources. Carefully characterize your slots in
terms of the kinds of entities that appear as slot-fillers.  Your
first step in this exercise should be to acquire a reasonably sized
corpus of stories that instantiate your template.



### Chapter 24

• Page 833: Change <reprompt\> to <reprompt/>
• Pages 833, 834, and 835, Figures 24.11, 24.12, and 24.13: All cases of <value expr="..."> should be <value expr="..."/>
• Page 835, Figure 24.13: There should be no space before the keyword CDATA.

### Chapter 25

• page 860 Figure 25.1, the first "the" in the fourth row should be white rather than gray
• page 866 line -2 "xiáo" should be "xiào"
• page 896 Figure 25.31, in candidate 2, the words "to", "forever", "party", "that", and "the" should also be highlighted/boxed in gray.