****     ERRATA     ****

         ERRORS etc. found by us in the textbooks

* Dexter C. Kozen, Automata and Computability, 1997,
  ISBN 0-387-94907-0, Springer Verlag.
* John E. Hopcroft and Jeffrey D. Ullman,
  Introduction to Automata Theory, Languages and Computation, 1979,
  Addison-Wesley.

Unless stated otherwise, these comments concern the book of Kozen.


p. 131, l. 6..8
  It is incorrectly stated that a grammar is ambiguous if there exist
different derivations of the same string.
"Derivations" should be replaced by "leftmost derivations".
(Equivalently, by "rightmost derivations" or "parse trees").


p. 25, par. 2, the first two sentences (on efficiency of
nondeterministic algorithms).
   The notion of efficiency meant here has nothing to do with any
intuitive notion of efficiency of a computation, for instance with the
total time of the computation.


p. 36  The usage of Lemma 6.1 in the proof of 6.3 is not needed.
Instead one can use (6.2) and the property from p. 33, lines -9..-7
("-"  means that lines are counted from the bottom).


p. 37, Example 6.6
   Not a good illustration for usefulness of epsilon transitions.  
A simpler automaton for this language is an NFA (without epsilon
transitions) with two start states (see. Ex. 5.2).


p. 45, par. 2  "An amazing and difficult to prove fact ..."
Not so difficult.  Follows almost immediately from closedness of
   regular languages under complement and equivalence of finite automata
and regular expressions.  (Conf. p. 46).


p. 65, l. -12,-11   "epsilon-closure described in Lecture 6"
It is described in Miscellaneous Exercise 10.


p. 167, par.2 "By a simple construction from Lecture 21 ..."
   Not so simple.  (A rather sophisticated conversion of a grammar to
Greibach normal form.)


p. 179, l. 12 (this chapter is outside of the scope of our lectures)
  It seems that  "Let  x  be any input"  should be augmented by
"on which  M  loops infinitely".


p. 190, l.-4  "An early paper on parsing is Knuth [71]"
I disagree with "early".  That paper seems to conclude a vivid area on
research on shift-reduce parsing (by providing a most powerful method).


p. 224, Counter Automata, l. 2
  "input head" should be "input tape".


p. 304, Homework 4 2.  A dot (·) is used to denote concatenation of
languages.  (This differs from the generally used notation, introduced
on p. 10.


p. 336, Ex.84(d).  
   This language cannot be shown non context-free using the knowledge
from the book, I believe.  (Please let me know if you can disprove
this opinion).  A tool applicable here is Ogden's lemma, see e.g. 
the book by Hopcroft & Ullman, p. 129.
................


The book by Hopcroft & Ullman, p. 87, the section on ambiguity,
paragraph 2, l.2,3. 
  The sentence   "From each derivation tree ..."  is true only if the
yield of the tree is a string of terminals.  (In other words, if no
nonterminal is a leaf of the tree.)


..., p. 251, Theorem 10.9.  A requirement is missing that the grammar
does not have useless symbols.

[2012, September,  © W. Drabent]