A Second Course in Formal Languages: Errata

• Page 34, line -6: Replace 2x by 2 |x|. (Pavel Bakhilau)

• 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₁".

• 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₁".

• Page 62, line 12: the transducer T has the order of the items listed incorrectly; it should read (Q, Σ, Γ, q₀, 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 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₅, replace q₁ → q with q₁ → q₂. (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 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 84: change the k in line 19 to n - 1.

• 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 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 121, line 2: change "before see" to "before, we see".

• Page 122, Example 4.6.2 (a). The L₁ should be L₀. (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 164, line 2: replace "substring" with "subword".

• Page 167, line -4: the arrow goes the wrong way in B → δ₃ A δ₄ .

• 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 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 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".