Some Errata to John C. Martin - Introduction to Languages and The Theory of Computation Fourth Edition Version of 12 December, 2020 (of this list of errata). =========================================================================== page 19, line -5 `Familar' should be `Familiar' page 36, Exercise 1.13(b) `r>0' shoulde be `r>0}' page 38, Exercise 1.22, line 4 `A is the smallest subset of A' should be `A is the smallest subset of U' page 42, Exercise 1.59 `Example 1.11' should be `Example 1.16' page 55, line -4 of proof Theorem 2.15 `Exercise 2.12' should be `Exercise 2.11' page 56, Figure 2.17(d) The arrow with label $b$ from the initial state to the accepting state should be reversed (cf. Figure 2.17(b) and (c)). page 60, line -4 `because $aab$ and $a$' should be `because $aab$ and $b$' page 84, Exercise 2.38(b) In the last of the three expressions, `{a,b}^*' should be `{a,b}' page 95, line 8 `Every string $x$...' should be `Every nonnull string $x$...' page 96, line 8 `the abbreviations $d$ and $l$' should be `the abbreviation $d$' (since we do not need $l$) page 101, line 9 `delta(0,a)' should be `delta(3,a)' page 103, line 4 `The set $\Lamda(\{s\})$ shoulde be `The set $\Lamda(\{v\})$ page 120, Exercise 3.16(a) `Show that the order' should be `Show that if $L$ is a nonempty regular language, the order' page 127, Exercise 3.50 `with appropriate labels' should be `with appropriate labels (except that none of the states in the diagram appearing first will be designated as accepting).' page 139, Figure 4.12 The edge between states $S$ and $B$ with label $a$ should be directed: from $B$ to $S$. page 140, line -7 `For every language $L \subset \Sigma^{*}$' should be `For every language $L \subseteq \Sigma^{*}$' page 154, step 5 The two CFGs in this step are not complete. In both CFGs, the productions $X_{a} \rightarrow a$, $X_{b} \rightarrow b$ and $X_{c} \rightarrow c$ are missing. page 157, Exercise 4.16 The second production in the CFG should be $S \rightarrow bSaS$. page 159, Exercise 4.31(a) The answer for the given string is 0, because neither of the symbols $/$ and $-$ appears in the grammar. To make the exercise a little more interesting, change the string to $a+(a+a)+a+a$. page 160, Exercise 4.42 `if $x$ is a balanced string' should be `if $x$ is a nonnull balanced string' page 161, Exercise 4.48 `Definition 4.7' should be `Definition 4.26' page 181, line -15 `$(q_{0},B\beta)$' should be `$(q_{0},\Lambda,B\beta)$' page 195, line 1 `Example 5.11' should be `Example 5.32' page 200, Exercise 5.25(b) `{0,1}^*' should be `{a,b}^*' page 202-203, Exercise 5.40 The given grammar is ambiguous. Although it is indeed possible to factor the grammar, this will not yield an LL(1) grammar, as the resulting grammar will still be ambiguous. page 206, line -6 `According to Theorem 4.31...' should be `According to Theorem 4.30...' page 207, line -4 `(Figure 6.1 illustrates...' should be `(Figure 6.2 illustrates...' page 210, line -15 `has exactly $n+1$' should be `has exactly $n+1$ letters' or `has exactly $n+1$ a's' or `has length exactly $n+1$' page 222, Exercise 6.16 `CFG' in parts (b), (c) and (d) should be `CFL' page 224, line -3 A closing brace `\}' is missing at the end of the line. page 230, line -17 It is not consistent - to give the added transition to $h_{r}$ which is drawn here a label `$\Delta/\Delta$,R' - and to say that both tape head and current symbol stay unchanged in line -11. I would propose to replace the R in line -17 by S. page 232, Figure 7.5 This figure should be called Figure 7.6. Two reasons for this: - the numbering of examples surrounding the figure: Example 7.5 and Example 7.7 - the reference to Figure 7.6 in Exercise 7.1 page 236, Figure 7.11 - the second label on the transition from $q_{1}$ to $q_{8}$ should be `$B/B$,R' instead of `$B/A$,R' - the transition from $q_{3}$ to $q_{8}$ should have only one label: `$A/A$,R' (the label `$B/A$,R' is certainly incorrect) - the transition from $q_{5}$ to $q_{8}$ should have only one label: `$B/B$,R' page 238, Figure 7.15 The transition from $s$ to itself with label `$b/b$,R' is missing (cf. Figure 7.4(b)). page 238, line 2 (the caption of Figure 7.15) It seems to be inconsistent to write $L = \{a,b\}^{*}(\{ab\}\{a,b\}^{*}\cup\{ba\})$ here, while the same language is written as $L = \{a,b\}^{*}\{ab\}\{a,b\}^{*}\cup\{a,b\}^{*}\{ba\})$ in Example 7.3 and in line -10 of page 238 itself. page 242, Figure 7.22 The two arrows between $q_{a}$ and $q_{b}$ should be reversed. page 248, line 20 It is not necessary to explicitly write `finite' subset, because every subset of `(Q \cup \{h_{a},h_{r}\})\times ...' is finite (indeed, in the definition of a pushdown automaton, Definition 5.1, it is necessary to write `finite subsets'). page 250, line 4 `$P(L)$ contains $\Lambda$ \ldots' should be `If $L \neq \emptyset$, then $P(L)$ contains $\Lambda$ \ldots' page 252, proof of Theorem 7.31 * (not really an error, but a suggestion): It might be better to use the fourth tape to store bitstrings that did NOT lead to the rejecting state. First, as a stopping criterion, it is easier to check whether or not the tape contains at least one bitstring of length $n$ than to check whether or not the tape contains all of them. Second, the bitstrings could also be used to select the next bitstring to be simulated. Only the bitstrings that did not lead to the rejecting state are worth expanding with another bit. page 253, lines 16/17 `The crucial features' should be `Some crucial features'. - It is also crucial that it is possible to decompose the string $e(T)e(z)$ into $e(T)$ and $e(z)$. - It is of course also important that $e$ is algorithmically computable. It is not required to demand this explicitly. It follows from the first feature and the third feature that $e$ is computable. The following algorithm would suffice for $e$, with input $T$: - $w$ = emptystring while (true) do if $w$ is valid encoding of a TM $T_{0}$, then decode $w$ into $T_{0}$ if $T_{0}$ equals $T$ (upto some equivalences) then return $w$ fi fi $w$ is next bitstring od page 253, line 20 `at most one Turing machine' should be `at most one Turing machine with a given input alphabet $\Sigma$'. Because that is what the function $e$ from Definition 7.33 does. One bitstring may be the encoding of different Turing machines (and correspond to different languages), depending on the input alphabet. It is not so hard to find a meaningful example. page 254, line -2 The first encoded move 111010111010100 should be 1110101111010100 page 255, Theorem 7.36 This result cannot be correct, given * that the states of a TM can be numbered in different ways, and the moves can be considered in any order (as is correctly mentioned in lines 1-2) * and that $e$ is an encoding FUNCTION, which means that only one of the infinitely many possible bitstrings resulting from the previous observation equals $e(T)$. Instead, one might say: `For every $x \in \{ 0, 1 \}^{*}$, $x$ represents a Turing machine, if and only if ...' page 256, line 19 `1110' should be `111', because * there is no reason to write 0 here * there is no 0 in the example that follows page 256, both line -16 and line -8 The first encoded move 111010111010100 should be 1110101111010100 page 259, lines 9/10 The four occurrences of $\Sigma$ should be $\Gamma$. page 260, Figure 7.38 The two-headed transition at the bottom of the picture should only be from right to left. page 269, line -1 `Consider the strings of $L$ in canonical order' should be `Consider the strings of $\Sigma^{*} in canonical order$ page 272, line -8 The order of the productions $CA \rightarrow AC$ and $CB \rightarrow BC$ is inconsistent with the order of these productions on page 278, line 10. page 274, line -5 Should end with: $q_{0}(\Delta\Delta)(bb)(aa)(\Delta\Delta)$ instead of $(\Delta\Delta)q_{0}(bb)(aa)(\Delta\Delta)$ page 274, line -3 Should begin with: $q_{0} \Delta b a \Delta)$ instead of $\Delta q_{0} b a \Delta)$ page 275, line 11 `Figure 8.1' should be `Figure 8.15' page 278-279, Definition 8.18 Probably, the special symbols $[$ and $]$ are supposed not to be written on the tape at positions between their original positions. page 280, line 15-17 One type of variables is missing in the list of variables: the states of the TM. page 281, line 5 This production is equal to the one in line 3. It should be $p(\sigma_{1} [ a) (\sigma_{2} \sigma_{3} ]) \rightarrow (\sigma_{1} [ b) q(\sigma_{2} \sigma_{3} ])$ instead. page 285, line -3 $B = \{ b_{j_{0}}, b_{j_{1}}, \ldots \}$ should be $B = \{ a_{j_{0}}, a_{j_{1}}, \ldots \}$ page 287, line -12/-11 The formulation `Let ${\cal T}$ represent the set of Turing machine with input alphabet $\Sigma$. A TM $T \in {\cal T}$ can be represented by the string $e(T) \in \{ 0, 1 \}^{*}$, and a string can represent at most one TM in ${\cal T}$. Therefore, ...' seems to be better. A string $e(T)$ only specifies the transitions from $T$, not the input alphabet, as Martin seems to realize himself in line -5. It would be even better to use ${\cal T}_{\Sigma}$ instead of ${\cal T}$ page 291, Exercise 8.12 `if and only if there is' should be `if and only if either $L$ is finite or there is' page 293, Exercise 8.25 `six' should be `nine' page 294 Exercise 8.35 is not appropriate, as its solution is already provided in the proof of Theorem 8.25. (Indeed, in the third edition, this was different.) page 295/297 Exercise 8.41(g) and Exercise 8.47(b) are the same. Probably, Exercise 8.47(b) should be: The set of all nonincreasing functions from N to N. as that exercise is more challenging. page 310, line 7 `AcceptsEverythingy' should be `AcceptsEverything' page 311, lines -8 to -4 The sentence beginning `If it reaches' should be modified as follows: `If it reaches $q$ the second time without having written a nonblank symbol, consider two cases: If the tape head is at least as far to the right as it was the first time $q$ was reached, $T$ will continue forever to repeat the finite sequence of moves that brought it from $q$ back to $q$, and the tape will remain blank; if the tape head is farther to the left the second time $T$ reaches $q$, $T$ will eventually fall off the tape and reject without having written a nonblank symbol.' page 312, line 10 `every Turing machine having property $R$' should be `every Turing machine $T$ having property $R$' because $T$ is referred to at the end of the sentence. pages 316-319, proof of Theorem 9.16 It is assumed that $T$ never halts in the reject state (page 316, line -19), and this assumption is used on page 319, line -7. This assumption does not seem to be necessary. If $T$ rejects, then at that point, the partial match simply cannot be extended (regardless of the type of rejection: move to $h_r$, no transition specified, walk off the tape). It certainly cannot become a match then. This is exactly what happens in the first case considered in Example 9.18. Indeed: no-instance of Accepts becomes no-instance of MPCP pages 316-319, proof of Theorem 9.16 It is assumed that $w \neq \Lambda$ (page 316, line -11). The case $w = \Lambda$ is treated separately on page 320, line 5. It does not seem to be necessary to make this assumption and to treat this case separately. We could as well start with the initial pair $(#,# q_{0} \Delta w#) = (#,# q_{0} \Delta #)$. This notation is not really more complicated than $(#,# q_{0} #)$ page 318, line -10 $\beta$ should be $\beta'$ page 319, line 3 $\alpha$ should be $\alpha'$ page 319, line 4 $\beta$ should be $\beta'$ page 319, line 5 $\beta$ should be $\beta'$ page 320, Example 9.18 This example is not consistent with the proof of Theorem 9.16. The TM depicted will crash for input string $w = \Lambda$. The proof of Theorem 9.16 assumes that $T$ never rejects. pages 321 and 322 The numbering in $c = c_{i_{1}} c_{i_{2}} \ldots c_{i_{k}}$ on page 321, line -3 is not really natural, as it does not reflect the order in which the $c_{i}$'s are introduced into the string. It would be more natural to use $c = c_{i_{k}} \ldots c_{i_{2}} c_{i_{1}}$. Moreover, in the proof of Theorem 9.20, a yes-instance of PCP could then be characterized by an equality $\alpha_{i_{1}} \alpha{i_{2}} \ldots \alpha_{i_{k}} = \beta_{i_{1}} \beta{i_{2}} \ldots \beta_{i_{k}}$, which is consistent with Definition 9.14. page 323, lines -11 and -10 One may wonder if there is any difference between the languages $A$ and $A_{1}$... page 327, Exercise 9.13d `every two finite subsets' should be `every two finite, non-empty subsets' (if $U$ is empty, and $S$ is not, then it is not true that $P_{S} \leq P_{U}$) page 329, Exercise 9.21 `not recursively enumerable' should be `recursively enumerable' page 331, line 2 `In the same way that most languages ... are not decidable,'' should be `In the same way that most languages ... are not recursively enumerable,'' or `In the same way that most languages ... are not recursive,'' Decidability is a property of decision problems. page 331, line -5 `For each $k \geq 1$' should be `For each $k \geq 0$'. Otherwise, there are no functions with 0 arguments at all, and you cannot define a recursive function with one argument. Moreover, Exercises 10.10 and 10.13 explicitly use constant functions with 0 arguments. page 332, Definition 10.2 It seems to be inconsistent to speak of `partial functions' in Definition 10.2(1) and to speak of `functions' in Definition 10.2(2). Given the discussion following Definition 10.2, it should probably be `partial functions' in both cases. page 336, line -14 `are primitive recursive functions from $N^m$ to $N$' should be `are primitive recursive functions from $N^n$ to $N$' page 339, line 3-4 `or even a function $k(x)$' should be `or even a computable function $k(x)$' Because there is a (non-computable) function $k(x)$ that would suffice: $k(x)$ = the number of moves of $T_{u}$ to halt on input $s_{x}$, if $T_{u}$ halts on input $s_{x} = 0, if $T_{u}$ does not halt on input $s_{x}$ pages 339-340, proof of Theorem 10.10 It seems to be inconsistent to define a function $f_{1}$ and not to use it directly to prove that $E_{P}$ is primitive recursive page 341, line -12 A simpler function $h$ would be z if $z \leq y$ h(X,y,z) = y+1 if $z \geq y+1 \wedge P(X,y+1)$ is true y+2 if $z \geq y+1 \wedge \neg P(X,y+1)$ is true page 346, line 2 `$M(x,i,y) = Mod(x, PrNo(i)^y)...$' should be `$M(x,i,x) = Mod(x, PrNo(i)^x)...$' page 349, lines 2 and -5/-6 It is a bit confusing to use a variable $n$ in the definition of IsConfig_T and Result_T, because $n$ is the number of arguments of our function $f$. It would be more appropriate to use a variable $m$ in these two definitions. page 349, lines -5/-6 (not really an error, but a suggestion): It is not necessary to let the function Result depend on T. We might as well simply define Result(m) = HighestPrime(Exponent(2,m)) (for every m) page 349, line -3 As `the number of the largest prime factor' of k=1 is not really defined, we should specify a default value for that case also, e.g., HighestPrime(0) = HighestPrime(1) = 0 page 350, line -8 `NewTapeNum' should be `NewTapeNumber' (see line -15 and see Exercise 10.35) page 351, line 2 The function Moves_T is a function from $N^{2}$ to $N$, and not from $N$ to $N$. page 351, lines 3/4 It might be more natural to simply define Moves_T(m,0)=m (for every m) because no-move implies no-change. page 351, line 5 `Moves(m,k)' should be `Moves_T(m,k)' page 351, line 14 `Accepting_T' should be `IsAccepting_T' page 351, line 14 The use of a variable $k$ in the unbounded minimalisation is not consistent with Definitions 10.14 and 10.15. A variable $y$ would be better. The variable $k$ is often used for the last argument in the operation of primitive recursion. page 351, line -10 Formally, InitConfig^{(n)}(X) is not a configuration, but a configuration number. page 351, line -8 In this edition of the book, the accepting configuration should be denoted as the string h_{a} \Delta 1^{f(X)} page 352, lines 9-11 The specification of a grammar computing a function as a four-tuple $G=(V,\Sigma,S,P)$ is a bit strange. A seven-tuple $G=(V,\Sigma,A,B,C,D,P)$ would be more appropriate, because - the start symbol $S$ is not really relevant (possibly only to generate start strings of the form $A x B$) - the symbols $A,B,C,D$ are more important to specify the function computed by $G$. Of course, if we use this seven-tuple, we should no longer say `if there are variables $A$, $B$, $C$ and $D$' but `where $A$, $B$, $C$ and $D$ are variables' Note that with the current definition, the same grammar $G=(V,\Sigma,S,P)$ may compute different functions, depending on the symbols $A$, $B$, $C$ and $D$ chosen. page 354, line 16 `$f_{12}$ is obtained from $f_{6}$ and $f_{12}$ by composition' should be `$f_{13}$ is obtained from $f_{6}$ and $f_{12}$ by composition' page 356, line 1 `2^x' should be `2^n' page 357, lines 3 and 6 Both occurrences of `t' should be `tn', to be consistent with line 8 (and with the variable $tn$ on page 349). page 357, line 8 As the symbol $k$ is often used in the definition of primitive recursion (as the value of the last argument), it would be better to use another symbol (say $m$) to count the number of arguments of the function $t$. page 383, Exercise 11.1 `Show that if' should be `Show that' page 415, lines 1-10 The productions introduced here, are not of the right form. According to the specification of Exercise 8.32, it is only allowed to substitute a variable $A$ (in the desired context) by a non-null string $X$. According to the productions introduced here, we may substitute a terminal ($c,b,a,d,e,f,g$) by a variable $Y_{i}$. A correct solution would be to first replace each terminal $\sigma$ occurring in a production by a corresponding variable $X_{\sigma}$, and to add productions of the type $X_{\sigma} \rightarrow \sigma$. Then $\alpha = A_{1} A_{2} \ldots A_{k}$, and the first step of the solution yields $X_{1} X_{2} \ldots X_{k}$. Now, the second step (in lines 1-10 of page 415) can be skipped. We only need the last step to convert $X_{1} X_{2} \ldots X_{k}$ into $\beta = Z_{1} Z_{2} \ldots Z_{k-1} Z_{k} \ldots Z_{m}$.