For each S-transition
δ (q i , a) = (q j , b, S),
we put into the corresponding transitions
and
for all c ∈ Γ.
It is reasonably obvious that every computation of M has a corresponding
computation of , so that can simulate M.
Simulation is a standard technique for showing the equivalence of automata,
and the formalism we have described makes it possible, as shown in the above
theorem, to talk about the process precisely and prove theorems about
equivalence. In our subsequent discussion, we use the notion of simulation
frequently, but we generally make no attempt to describe everything in a
rigorous and detailed way. Complete simulations with Turing machines are often
cumbersome. To avoid this, we keep our discussion descriptive, rather than in
theorem-proof form. The simulations are given only in broad outline, but it
should not be hard to see how they can be made rigorous. The reader will find it
instructive to sketch each simulation in some higher-level language or in
pseudocode.
Figure 10.1