At this point the Turing machine halts in a final state, so the string aabb is
accepted.
You are urged to trace this program with several more strings in L, as well as
with some not in L.
Example 9.8
Design a Turing machine that accepts
L={a n b n c n : n ≥1}.
The ideas used in Example 9.7 are easily carried over to this case. We match
each a,b, and c by replacing them in order by x,y, and z, respectively. At the end,
we check that all original symbols have been rewritten. Although conceptually a
simple extension of the previous example, writing the actual program is tedious.
We leave it as a somewhat lengthy, but straightforward exercise. Notice that even
though {a n b n }is a context-free language and {a n b n c n } is not, they can be
accepted by Turing machines with very similar structures.
One conclusion we can draw from this example is that a Turing machine can
recognize some languages that are not context-free, a first indication that Turing
machines are more powerful than pushdown automata.
Turing Machines as Transducers
We have had little reason so far to study transducers; in language theory,
accepters are quite adequate. But as we will shortly see, Turing machines are not
only interesting as language accepters, they also provide us with a simple