Some Errata to
John C. Martin - Introduction to Languages and The Theory of Computation
Fourth Edition
Version of 8 November, 2016 (of this list of errata).
===========================================================================
page 19, line -5
`Familar'
should be
`Familiar'
page 56, Figure 2.17(d)
The arrow from the initial state to the accepting state with label $b$
should be reversed (cf. Figure 2.17(b) and (c)).
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 103, line 4
`The set $\Lamda(\{s\})$
shoulde be
`The set $\Lamda(\{v\})$
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 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 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 269, line -1
`Consider the strings of $L$ in canonical order'
should be
`Consider the strings of $\Sigma^{*} in canonical order$
page 260, Figure 7.38
The two-headed transition at the bottom of the picture should
only be from right to left.
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, line -2
`Show that a set $L \subseteq \Sigma^{*}$ is recursive'
should be
`Show that a set $L \subseteq \Sigma^{*}$ is infinite and recursive'
$L$ must be infinite, because the function $f$ is total and increasing.
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.41g and Exercise 8.47b are the same.
Probably, Exercise 8.47b 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, line -7
It is not necessarily true that, if $T$ reaches $q$ the second time
without having written a nonblank symbol, the tape head is at least
as far to the right as it was the first time $q$ was reached.
$T$ could have moved to the left in between.
However, this does not really matter: in this case, $T$ wil continue
to repeat the finite sequence of moves that brought it from $q$ back
to $q$, not writing a nonblank symbol, until it falls off the tape.
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 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
Is 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 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}$.