- Page 3, Line 12: not quite an error, but this would be the appropriate place to say that
*x*^{0}= ε for all strings*x*. (Kevin Wolf) - Page 10, line -7: remove parens around "see Exercise 28".
(Curtis Bright).
- Page 20, statement of Theorem 1.8.1. It should read:
"If
*L*_{2}∈ P and*L*_{1}≤*L*_{2}, then*L*_{1}∈ P." (Stephen Checkoway) - Page 28, lines -1, -2: I should have said explicitly that
*w*[*i*..*i*-1] = ε . - Page 34, line -6: Replace 2
*x*by 2 |*x*|. (Pavel Bakhilau) - Page 35, line 2 of the proof of Theorem 2.4.2. Repalce
"there exists" with "there exist".
- Page 35, end of first paragraph of proof of Theorem 2.4.3.
Add "So
*x*≠*z*." at the end of the paragraph. - Page 48, line 7: Replace "Theorems 2.3.5" with "Theorem 2.3.5" (Curtis
Bright)
- Page 48, line -1: Insert a space between "site," and the URL.
(Curtis Bright)
- Page 57: In Example 3.3.8, it probably would have been clearer to give a
formal definition of shuff, namely,

shuff(*x*,*y*) = {*x*_{1}*y*_{1}*x*_{2}*y*_{2}...*x*_{n}*y*_{n}: there exists a decomposition*x*=*x*_{1}*x*_{2}...*x*_{n}and*y*=*y*_{1}...*y*_{n}for (possibly empty) words*x*_{1},*x*_{2}, ...,*x*_{n},*y*_{1},*y*_{2}, ...,*y*_{n}}. - Page 60, line -9: it would be clearer if "a final state has been
reached" were replaced with "we have reached the end of
*x*_{1}". - Page 61, lines 5-6: it would be clearer if "until it reaches a final
state
*q*_{f}∈*F*" were replaced with "until we guess we have reached the end of*x*_{1}". - Page 62, line 12: the transducer T has the order of the items
listed incorrectly; it should read (Q, Σ, Δ, q
_{0}, F, S) instead. - Page 63: in line 9 and in the first line of the
statement of Theorem 3.5.3,
*f*should be a map from Σ^{*}to 2^{Δ*}. (Nick Bowler) - Page 63: in line 5 of the proof of Theorem 3.5.3,
replace Σ with Σ
^{*}. - Page 63: in lines 8-9 of the proof of Theorem 3.5.3, there is a bit
of unclarity. Replace "where each transition in
*T*, (*p*,*x*,*y*,*q*) ∈*S*is replaced with δ(*p*,*a*_{x,y}) =*q*in*M*" with "where each transition in*T*of the form (*p*,*x*,*y*,*q*) ∈*S*is replaced by a transition from*p*to*q*in*M*labeled*a*_{x,y}". (Gregor Richards) - Page 64: In the statement of Theorem 3.5.6, fix the domain and
range so it says
*f*: Σ^{*}→ 2^{Δ*}. (Curtis Bright) - Page 64: In the statement of Theorem 3.5.6, the last line
should read "Then so is
*g*°*f*." (Abel Molina Prieto and Meng He) - Page 72, line 3: change ``
*w*=*n*'' to ``|*w*| =*n*''. (Nick Bowler) - Page 73, Figure 3.15: In the state labeled
*p*_{5}, replace*q*_{1}→*q*with*q*_{1}→*q*_{2}. (Martin Kess and Carmen Bruni) - Page 75, line -16: it should read, "... let
*M*be the incidence matrix of*A*'." (the prime is missing) - Page 77, line 6: replace
*xy ∈ L(M)*with*xy ∈ L(A)*(Sean Nyman and Pavel Bakhilau) - Page 79, line -6: replace
*M*with*M'*. (Curtis Bright) - Page 81: the last entries in lines 3 and 4 of
the table at the top of the page are wrong. Replace the final "1" by
"2" twice.
- Page 83: The proof of Theorem 3.10.2 is sloppy and it should
be replaced by the one below.
- Page 84: change the
*k*in line 19 to*n*- 1. (This is obsolete because you should simply replace the whole proof of Theorem 3.10.2 as above.) - Page 90, 4th bullet in the proof of Theorem 3.11.1 should read
δ''([
*p*,*q*],a) = [δ(*p*,*a*), δ'(*q*,*a*)]. (The prime on the second δ on the rhs is missing.) (Carmen Bruni) - Page 90, line -3, replace
*j*',*j*' with*j*,*j*'. (Carmen Bruni) - Page 93, line -7: replace "is regular" with "are regular".
- Page 96, exercise 4: replace {0, 1, ..., k-1} in the first line
of the exercise with {0, 1, ..., k-1}^* (Jurriaan Rot and Hendrik Jan
Hoogeboom)
- Pages 97-98: In exercises 3.15 and 3.16, there is no reason to assume
that the substituted languages are regular; they can be arbitrary.
(Jurriaan Rot)
- Page 100, in exercise 32, replace "Example 3.12" with "Example 3.12.6".
(Curtis Bright)
- Page 103: In exercise 61, the definition of
*r*(*L*) should have curly braces around*r*(*x*). (Curtis Bright) - Page 104: In exercise 68, the definition of palc(
*L*) should be a union, not an intersection. (Curtis Bright) - Page 116: In lines 4 and 5, change "production" twice to
"derivation". (JOS, March 6 2017)
- Page 116, in the very last line of the proof of Theorem 4.4.1,
change the
`b`to`c`. (Meng He) - Page 118, first line of the proof of Lemma 4.5.2: Insert "the"
between "be" and "root".
- Page 120, line -3: Change
*L*to*L*_{6}. (Curtis Bright). - Page 121, line 2: change "before see" to "before, we see".
- Page 121, line 2: change
*L*to*L*_{6}. (Curtis Bright). - Page 122, Example 4.6.2 (a). The
*L*_{1}should be*L*_{0}. (Rick van der Zwet) - Page 124, line 4: Insert ≥ before
*j*(*k*+1) + 1 on this line. - Page 124, line 5: replace "backup" with "back up".
- Page 125, line -9: replace
*v' v w x x'*with*v' v w' x x'*. - Page 126, last line of Example 4.6.6: The very last membership
symbol should have a slash through it, that is, it should
be "not a member of" instead of "member of".
- Page 127: in the first line of the page, replace "two
non-ε moves" with "two moves on the same symbol of the alphabet,
or ε".
- Page 132, Exercise 4: in the displayed equation the right curly
brace is in the wrong place; it should be at the end. (Chen Fei Du)
- Page 136, Exercise 33 (f): Change "equivalence relation" to
"equivalence class". (Curtis Bright)
- Page 141, beginning of Section 5.1: change "an CFG grammar" to "a CF
grammar". (Ian Charlesworth)
- Page 164, line 2: replace "substring" with "subword".
- Page 167, line -4: the arrow goes the wrong way in
*B*→ δ_{3}*A*δ_{4}. - Page 179, line -4. There is a missing
"Hence" right before equation (6.1).
- Page 185, in Figure 6.2, the heading of the second column
should read Σ(
*n*). (N. Rampersad) - Page 187: in line -5, it should read "...to denote that
*g*(*i*) =*w*_{i}for..". (Richard Peng) - Page 187, in the definition of
*h*in lines 6-8, replace the second occurrence of*h*(`2`) with*h*(`3`). (N. Rampersad) - Page 190, in line -9, change
"automatons" to "automata".
- Page 193: In the proof of Theorem 6.6.7, line 4, remove
an extra copy of Q in the union. (JOS, March 29 2017)
- Page 202, line 2: replace "CLs" with "CSLs". (N. Rampersad).
- Page 202. Replace "CFG" with "CSG" in the first line of
Example 7.1.1. (Nick Bowler)
- Page 202. The example CSG in Example 7.1.1 is actually wrong;
it can generate (for example) the string
aabbbbcc. A correct grammar is, for example,
S → ABSc

S → Abc

BA → XA

XA → XY

XY → AY

AY → AB

A → a

Bb → bb

- Page 207. At the bottom of the page, add the rule for a right
move [pX♭] → [Yq♭]. (Hendrik Jan Hoogeboom)
- Page 215. In Example 7.3.3, the pattern-matching
language should have
*x*in {a,b}^{+}and*y*in {a,b}^{*}. - Page 226. In the title of
Brzozowski [1962a], replace the second occurrence
of "regular" with "definite". (Zhi Xu)
- Page 229. In the title of Nozaki [1979], replace "nondeterministic"
with "non-deterministic".