Σ*,
implies that
and vice versa.
The first part is to show that, whenever the npda is such that the symbol A
and its effects can be removed from the stack while reading u and going from
state q i to q j , then the variable (q i Aq j ) can derive u. This is not hard to see since
the grammar was explicitly constructed to do this. We only need an induction on
the number of moves to make this precise.
For the converse, consider a single step in the derivation such as
Using the corresponding transition for the npda
we see that the A can be removed from the stack, BC put on, reading a, with the
control unit going from state q i to q j . Similarly, if
then there must be a corresponding transition
whereby the A can be popped off the stack. We see from this that the sentential
forms derived from (q i Aq j ) define a sequence of possible configurations of the
npda by which (7.7) can be achieved.
Note that (q i Aq j ) ⇒ a(q j Bq l ) (q l Cq k ) might be possible for some (q j Bq i )
(q i Cq k ) for which there is no corresponding transition of the form (7.8) or (7.10).
But, in that case, at least one of the variables on the right will be useless. For all
sentential forms leading to a terminal string, the argument given holds.
If we now apply the conclusion to
implies that
and vice versa.
The first part is to show that, whenever the npda is such that the symbol A
and its effects can be removed from the stack while reading u and going from
state q i to q j , then the variable (q i Aq j ) can derive u. This is not hard to see since
the grammar was explicitly constructed to do this. We only need an induction on
the number of moves to make this precise.
For the converse, consider a single step in the derivation such as
Using the corresponding transition for the npda
we see that the A can be removed from the stack, BC put on, reading a, with the
control unit going from state q i to q j . Similarly, if
then there must be a corresponding transition
whereby the A can be popped off the stack. We see from this that the sentential
forms derived from (q i Aq j ) define a sequence of possible configurations of the
npda by which (7.7) can be achieved.
Note that (q i Aq j ) ⇒ a(q j Bq l ) (q l Cq k ) might be possible for some (q j Bq i )
(q i Cq k ) for which there is no corresponding transition of the form (7.8) or (7.10).
But, in that case, at least one of the variables on the right will be useless. For all
sentential forms leading to a terminal string, the argument given holds.
If we now apply the conclusion to