qj. Subsequently, we gofrom q j to q i , erasing B, then from q i to q k , erasing C.
In the last step, it may seem that we have added too much, as there may be
some states q i that cannot be reached from q j while erasing B. This is true, but
this does not affect the grammar. The resulting variables (q j Bq l ) are useless
variables and do not affect the language accepted by the grammar.
Finally, as a start variable we take (q 0 zq f ), where q f is the single final state of
the npda.
Example 7.8
Consider the npda with transitions
Using q 0 as the initial state and q 2 as the final state, the npda satisfies condition 1
above, but not 2. To satisfy the latter, we introduce a new state q 3 and an
intermediate step in which we first remove the A from the stack, then replace it
in the next move. The new set of transition rules is
The last three transitions are of the form (7.5) so that they yield the
corresponding productions
From the first two transitions we get the set of productions
In the last step, it may seem that we have added too much, as there may be
some states q i that cannot be reached from q j while erasing B. This is true, but
this does not affect the grammar. The resulting variables (q j Bq l ) are useless
variables and do not affect the language accepted by the grammar.
Finally, as a start variable we take (q 0 zq f ), where q f is the single final state of
the npda.
Example 7.8
Consider the npda with transitions
Using q 0 as the initial state and q 2 as the final state, the npda satisfies condition 1
above, but not 2. To satisfy the latter, we introduce a new state q 3 and an
intermediate step in which we first remove the A from the stack, then replace it
in the next move. The new set of transition rules is
The last three transitions are of the form (7.5) so that they yield the
corresponding productions
From the first two transitions we get the set of productions