As proved in the last chapter, the language consisting of strings
with a positive number of x’s followed by the same number
of y’s followed by the same number of zs is
not context free and so cannot be recognised by a pushdown automaton. We
can construct a Turing machine which recognises it though.
There are two stacks, one of which initially holds the input and the
other of which is initially empty. I’ll refer to these as Stack I and
Stack E, respectively. While only x’s y’s and
zs appear on the stacks initially it’s convenient to allow
the machine to push and pop X’s, Y’s and
Z’s as well.
There are two phases to the computation. In the first phase we perform the following action repeatedly:
If Stack E is not empty we pop symbols off of it and push them onto Stack I until Stack E is empty.
We pop symbols off of Stack I and push them onto Stack E until
the symbol we pop off of Stack I is an x. Once this happens
we push an X onto Stack E instead of an x and
move on to the next action. If Stack I becomes empty before we see an
x then we move on to the second stage of the
computation.
We pop symbols off of Stack I and push them onto Stack E until
the symbol we pop off of Stack I is a y. Once this happens
we push a Y onto Stack E instead of a y and
move on to the next action. If Stack I becomes empty before we see a
y then we halt and the computation is
unsuccessful.
We pop symbols off of Stack I and push them onto Stack E until
the symbol we pop off of Stack I is a z. Once this happens
we push a Z onto Stack E instead of a z and
move on to the next action. If Stack I becomes empty before we see a
z then we halt and the computation is
unsuccessful.
The second stage is simpler.
If Stack E is not empty we pop symbols off of it and push them onto Stack I until Stack E is empty.
We pop symbols off of Stack I one at a time and push them onto
Stack E. If any of these symbols is a y or a z
then we halt and the computation is unsuccessful.
If Stack I becomes empty without any y’s or
z’s having been seen then we halt and the computation is
successful.
Conceptually this is fairly simple. In the first stage we replace the
first x by an X, the first y by a
Y and the first z by a Z, then
the second x by an X, the second
y by a Y and the second z by a
Z, etc. If the input was in the languages then at this
point we should have with a positive number of X’s followed
by the same number of Y’s followed by the same number of
Zs. If it’s not in the language then either we have too few
y’s or z’s in the input or too many. If we
have too few then the machine will already have halted unsuccessfully
when it empties Stack I while scanning for a y or a
z. If we have too many then there will be some
y’s which didn’t get changed to Y’s or some
z’s which didn’t get changed to Z’s. In that
case the machine will halt unsuccessfully during the second stage.
Otherwise it will halt successfully after the second stage.
This Turing machine has the rather nice property that no matter what input we give it it will eventually halt, either successfully or unsuccessfully. This is not true of Turing machines in general. A recogniser is required to halt successfully on any input in the language and only on inputs in the language but it is allowed to halt unsuccessfully or run forever on inputs which are not in the language. A Turing machine which always halts unsuccessfully on inputs which are not in the language, like this one does, is called a decider for the language. Every decider is a recogniser, but not vice versa. In fact there are languages for which it’s possible to construct a recogniser but impossible to construct a decider.