A Second Course in Formal Languages: Errata

• Page 3, Line 12: not quite an error, but this would be the appropriate place to say that x⁰ = ε for all strings x. (Kevin Wolf)

• Page 5, Line -8: replace "headless" with "tailless". (Bjørn Kjos-Hanssen)

• Page 10, line -7: remove parens around "see Exercise 28". (Curtis Bright).

• Page 14, line -7: replace "q is scanning" with "M is scanning". (Bjørn Kjos-Hanssen)

• Page 20, statement of Theorem 1.8.1. It should read: "If L₂ ∈ P and L₁ ≤ L₂, then L₁ ∈ P." (Stephen Checkoway)

• Page 28, lines -1, -2: I should have said explicitly that w[i..i-1] = ε .

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

• Page 35, line 2 of the proof of Theorem 2.4.2. Replace "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 36. In the proof of Lemma 2.4.4, replace "ywz" with "ywv", "words y,z" with "words y,v", "wzy" with "wvy" (twice). (Patrick Au)

• 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₁ y₁ x₂ y₂ ... x_n y_n : there exists a decomposition x = x₁ x₂ ... x_n and y = y₁ ... y_n for (possibly empty) words x₁, x₂, ..., x_n, y₁, y₂, ..., 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₁".

• 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 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 63: In Line -2, replace Γ with Δ. (Patrick Au)

• 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 65: In the caption of Figure 3.10, the composition should be T₂ ° T'₁. (Patrick Au)

• 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 5: replace "2.376" with "2.373". (Bjørn Kjos-Hanssen)

• 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 -15: Replace "if z contained" with "if z properly contains". (Bjørn Kjos-Hanssen)

• Page 120, line -3: Change L to L₆. (Curtis Bright).

• Page 121, line 2: change "before see" to "before, we see".

• Page 121, line 2: change L to L₆. (Curtis Bright).

• Page 121: the definition of the morphism h has some typos. h(0) should be 0102012021012102010212. And h(1) should be 0102012021201210120212. (Bjørn Kjos-Hanssen)

• Page 122: the definition of ψ(L) is unnecessarily cumbersome. It should be ψ(L) = { ψ(w) : w ∈ L }. (Bjørn Kjos-Hanssen)

• 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 127: in the first line of the page, replace "two non-ε moves" with "two moves on the same symbol of the alphabet, or ε".

• Page 129: replace "see Exercise 1.22" with "see Example 1.5.2". (Bjørn Kjos-Hanssen)

• 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 140, line -4: Replace "2.376" with "2.373". (Bjørn Kjos-Hanssen)
• 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 → δ₃ 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 185, in table, line corresponding to n = 6: not strictly an error, but to be consistent it should have a > sign and not ≥. (Bjørn Kjos-Hanssen)

• 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, line 19: replace "to its left" with "immediately to its left". (Bjørn Kjos-Hanssen)

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