we say that C 2 is at least as powerful as C1. If the converse also holds and for
every M 2 in C 1 there is an M 1 in C 1 such that L (M 1 ) = L (M 2 ), we say that C 1
and C 2 are equivalent.
There are many ways to establish the equivalence of automata. The
construction of Theorem 2.2 does this for dfa's and nfa's. For demonstrating the
equivalence in connection with Turing's machines, we often use the important
technique of simulation.
Let M be an automaton. We say that another automaton can simulate a
computation of M if can mimic the computation of M in the following
manner. Let d 0 ,d 1 ,…be the sequence of instantaneous descriptions of the
computation of M, that is,
Then simulates this computation if it carries out a
where
…are instantaneous descriptions, such that each of them is
associated with a unique configuration of M. In other words, if we know the
computation carried out by
, we can determine from it exactly what
computations M would have done, given the corresponding starting
configuration.
Note that the simulation of a single move
of M may involve
several moves of . The intermediate configurations in
may not
correspond to any configuration of M, but this does not affect anything if we can
tell which configurations of are relevant. As long as we can determine from
the computation of what M would have done, the simulation is proper. If
can simulate every computation of M, we say that can simulate M. It should
be clear that if can simulate M, then matters can be arranged so that M and
accept the same language, and the two automata are equivalent. To demonstrate
the equivalence of two classes of automata, we show that for every machine in
every M 2 in C 1 there is an M 1 in C 1 such that L (M 1 ) = L (M 2 ), we say that C 1
and C 2 are equivalent.
There are many ways to establish the equivalence of automata. The
construction of Theorem 2.2 does this for dfa's and nfa's. For demonstrating the
equivalence in connection with Turing's machines, we often use the important
technique of simulation.
Let M be an automaton. We say that another automaton can simulate a
computation of M if can mimic the computation of M in the following
manner. Let d 0 ,d 1 ,…be the sequence of instantaneous descriptions of the
computation of M, that is,
Then simulates this computation if it carries out a
where
…are instantaneous descriptions, such that each of them is
associated with a unique configuration of M. In other words, if we know the
computation carried out by
, we can determine from it exactly what
computations M would have done, given the corresponding starting
configuration.
Note that the simulation of a single move
of M may involve
several moves of . The intermediate configurations in
may not
correspond to any configuration of M, but this does not affect anything if we can
tell which configurations of are relevant. As long as we can determine from
the computation of what M would have done, the simulation is proper. If
can simulate every computation of M, we say that can simulate M. It should
be clear that if can simulate M, then matters can be arranged so that M and
accept the same language, and the two automata are equivalent. To demonstrate
the equivalence of two classes of automata, we show that for every machine in