236 9 Theory of Computer Science
if the PDS has no symbols from r (since B can reach qf only by the
application of RJ. This suggests that T(B) = N(A).
Now we prove rigorously that N(A) =T(B). Suppose 11' E N(A). Then by
the definition of N(A), (qo. w, Zo) Hf (q. A. A) for some q E Q. Using R b
we see that
By Result 2,
(7.12)
By Result 1, we have
(7.13)
(q. A, Zo) hf (qt' A, A)
Combining (7.12)-(7.14). we have
(q'o, w, Zo) Hf (qt' A, A)
This proves that W E T(B), i.e. N(A) ~ T(B).
To prove T(B) ~ N(A) , we start with W ~ T(B). Then
(q'o· w. Z'O) HJ (qt' A, a)
(7.14)
(7.15)
But B can reach qr only by the application of R 3 • To apply R 3 • Z/O should be
the topmost element on PDS. Z'O is placed initially, and so when it is on the
top there are no other elements in PDS. So a = A, and (7.15) actually reduces
to
(7.16)
In (7.16), the initial and final steps are effected only by A-moves. The
intermediate steps are induced by the conesponding moves of A. So (7.16) can
be split as (q'o, Aw. Z/O) hf (qo, YV, ZOZ/ O ) Hf (q. A, Z'O) for some
q E Q. Thus, (q'o. Aw, Z(J) hf (qo, w. ZoZ(J) Hf (q, A, Z'o) hf (qt' A, A).
As we get (qo, w. ZoZ/ O ) Hf (q, A. Z'o) by applying R-; several times and R 2
does not affect Z'o at the bottom, we have (qo, w, Zo) Hf (q, A, A). By the
construction of R 2 • we have (qo, w. Zo) ~ (q. A, A). which means vI' E N(A).
Thus. T(B) ~ N(A). and hence T(B) = N(A) = L. I