Finally, in preparation for later chapters, we look at linear bounded automata.
These are Turing machines that have an infinite tape, but that can make use of
the tape only in a restricted way.
10.1 Minor Variations on the Turing Machine Theme
We first consider some relatively minor changes in Definition 9.1 and investigate
whether these changes make any difference in the general concept. Whenever we
change a definition, we introduce a new type of automata and raise the question
whether these new automata are in any real sense different from those we have
already encountered. What do we mean by an essential difference between one
class of automata and another? Although there may be clear differences in their
definitions, these differences may not have any interesting consequences. We
have seen an example of this in the case of deterministic and nondeterministic
finite automata. These have quite different definitions, but they are equivalent in
the sense that they both are identified exactly with the family of regular
languages. Extrapolating from this, we can define equivalence or
nonequivalence for classes of automata in general.
Equivalence of Classes of Automata
Whenever we define equivalence for two automata or classes of automata, we
must carefully state what is to be understood by this equivalence. For the rest of
this chapter, we follow the precedence established for nfa's and dfa's and define
equivalence with respect to the ability to accept languages.
Definition 10.1
Two automata are equivalent if they accept the same language. Consider two
classes of automata C 1 and C 2 . If for every automaton M 1 in C 1 there is an
automaton M 2 in C 2 such that
L (M 1 )= L (M 2 ),