FINITE AUTOMATA

This is the errata page for my book published in 2004
My thanks to the Japanese translator, Ryoma Sin'ya of Akita University,
for alerting me to the typos he has found in the course of his translation work.

 Page X. "Chapter~2, omitting Section~2.5, can be regarded as a collection of examples.” should read  "Chapter~2, omitting Section~2.6, can be regarded as a collection of examples.” Page 5. Exercise 1.1.1. It is better to use Italic font style for denoting aardvark. Page 13. Example 1.4.1. The sentence “HH and input the string aba Then” should read “HH and input the string aba, then” Page 39. Example 2.4.4. The last sentence: "It is now easy to draw the transition table of the required automaton” Transition table should read transition diagram. Page 43. Proof of Proposition 2.5.5. "But this is equivalent to s0 ·x ∈ F and t0 ·x ∈ G,” The word `and' should be be emphasised. Page 71. Proof of Proposition 3.3.6. "the strings u_1, (a_1u_2), . . . , (a_{n−1} u_n) is accepted by L(A)” should read "the strings u_1, (a_1u_2), . . . , (a_{n−1} u_n) is accepted by A” Page 72.  The 4th equation of Section 3.4. “L(A) = I \cdot A^* \cap T \neq \emptyset” should read “L(A) = \{ w \in A^* \mid I \cdot w \cap T \neq \emptyset \}" Page 89. Example 4.1.3. “We calculate $\A$ for the $\id$-automaton of …” should read “We calculate $\A^s$ for the $\id$-automaton of …” Page 92. The last sentence of the proof of Theorem 4.2.1. “It is easy to check that $L({\bf B}) = L$” should read “It is easy to check that $L({\bf D}) = L$” Page 115. The second line. "where $b$ and $c$ are known” should read "where $a$, $b$ and $c$ are known” Page 123 (middle). In the proof of Theorem 5.4.9. "By using the ith row of the equation X = CX + R,” should read "By using the ith row of the equation X' = C’X' + R’," Page 133. Example 6.1.7. “given by the transition table below:” should read “given by the transition diagram below:” Page 135. In the proof of Theorem 6.2.1-(1). "Finally, the set of terminal states is defined to be $T$” should read  "Finally, the set of terminal states is defined to be $T = T_1 \cup T_2$” Page 137.  The definition of $F(r)$. $F(r) = \{x \in A^{2} \colon \: A^{\ast} \cap L(r) \neq \emptyset \}$ should read $F(r) = \{x \in A^{2} \colon \: A^{\ast} x A^{\ast} \cap L(r) \neq \emptyset \}$ Page 141, line 6. "As we shall prove later in this section,’ should read  "As we shall prove later in this chapter," Page 150, Theorem 7. Forgot a fullstop in the statement. Page 155, in the proof of Theorem 7.4.2. "Now B is reduced,” should read “Now A and B are reduced,” Page 163, Example 7.5.10, Item (7). "By Proposition 7.5.4” should read “By Proposition 7.5.3” Page 168, Summary of Chapter 7, about minimal automata. “reduced and connected” should read “reduced and accessible” Page 181, Algorithm 8.2.5. "By construction, $| vw’ | < |w|$”. This is not true because a relation can have words with same length. “By construction, for the tree order $<$, $vw’ < w$” is ok. Page 192, Example 9.1.2. Forgot fullstop before “Here”. Page 201, Example 9.2.5. "Proposition 9.2.4” should read “Theorem 9.2.4” Page 206, 1st line (Example 9.2.14).  There is missing notation here. $\mathbb{Z}_{n}$ should be formally defined. Page 209, in the proof of Theorem 9.4.1. “Then $i \cdot (uxv) \in L$” should read “Then $i \cdot (uxv) \in T$" Page 214, Remarks on Chapter 9, 1st paragraph. The relation $\rho_\A$ is written as $\rho$ twice. Page 218, proof of Theorem 10.1.2. "$i, i+1, \ldots i + (k-1)$" -> "$i, i+1, \ldots, i + (k-1)$” (forgot a comma before $i+(k-1)$). Page 222, 1st paragraph. "$\pi_{1}, \pi_{2} \colon \: S \times T \rightarrow S$” should read "$\pi_{1} \colon \: S \times T \rightarrow S, \pi_{2} \colon \: S \times T \rightarrow T$” Page 222, Example 10.1.9. “Let $S_{1},S_{3},S_{3}$” should read “Let $S_{1},S_{2},S_{3}$”. Page 230, proof of Proposition 10.2.11. "be monoid homomorphisms such that and $L_{1} = \alpha_{1}^{-1}(P_{1})$ and $L_{2} = \alpha_{2}^{-1}(P_{2})$.”should read “be monoid homomorphisms such that $L_{1} = \alpha_{1}^{-1}(P_{1})$ and $L_{2} = \alpha_{2}^{-1}(P_{2})$ holds for some subsets $$P_{1} \subseteq M_{1}$$ and $$P_{2} \subseteq M_{2}$$." Page 253, proof of Theorem 11.4.2. "If $r = s'$ then $L(s)$ recognises $s'$ by Proposition~10.2.8(i);  in fact, in this case $L(s)$ is also the syntactic monoid of $s’$.” should read "If $r = s'$ then $M$ recognises $L(s’)$ by Proposition~10.2.8(i);”  in fact, in this case $M$ is also the syntactic monoid of $L(s’)$." Page 257, proof of Proposition 11.4.9, the last sentence. "Thus $\phi (u) = n \phi(a)$, where $n \phi(a)M = mM$. Thus $n = \phi (w) = \phi(u)\phi(v) = n \phi(a)\phi(v) \in mM$.” should read “Thus $\phi (u) = n' \phi(a)$, where $n' \phi(a)M = mM$ for some $n’ \in M$ and $a \in A$. Thus $n = \phi (w) = \phi(u)\phi(v) = n' \phi(a)\phi(v) \in mM$.” Page 260, the last equation. Forgotten a fullstop. Page 267, Examples 12.1.3-(4). "The proof of (VM2) follows from Lemma~11.2.13,” should read "The proof of (VM2) follows from Lemma~11.2.5,”. Page 270, after proof of Lemma 12.1.8. "The definition below is not an obvious one, although it is partially motivated by Lemma~12.1.7.” should read  "The definition below is not an obvious one, although it is partially motivated by Lemma~12.1.8.” Page 274, first sentence. "We shall now describe a method for describing pseudovarieties of semigroups.” should read "We shall now describe a method for describing pseudovarieties of monoids” (pseudovariety of semigroups has not yet been defined). Page 274, before Example 12.2.3. The notion “ultimately defined” has yet to have been defined. Thus add the following sentence after the definition of $\mathsf{M}’’$: “We say that $\mathsf{M}''$ is {\em ultimately defined} by the equations $(u_{n} = v_{n})_{n \geq 1}$.” Page 274, Example 12.2.3. “By Theorem 10.3.2,” should read “By Theorem 11.3.2,” Page 275, proof of Theorem 12.2.4. "Put $A_{n} = \{a_{1}, \ldots a_{n} \}$.” should read "Put $A_{n} = \{a_{1}, \ldots, a_{n} \}$.” Page 275, proof of Theorem 12.2.4, second paragraph. $A_n$ is written as $A$ twice. Page 276, Remarks on Chapter 12. "condition (VL1) is natural from the point of view of the results we proved back in Section~2.6;” should read "condition (VL1) is natural from the point of view of the results we proved back in Section~2.5;”