These restrictions may appear to be very severe, but they are not. It can be
shown that for any npda there exists an equivalent one having properties 1 and 2.
This equivalence is explored partially in Exercises 16 and 17 in Section 7.1.
Here we need to explore it further, but again we will leave the arguments as an
exercise (see Exercise 16 at the end of this section). Taking this as given, we
now construct a context-free grammar for the language accepted by the npda.
As stated, we want the sentential form to represent the content of the stack.
But the configuration of the npda also involves an internal state, and this has to
be remembered in the sentential form as well. It is hard to see how this can be
done, and the construction we give here is a little tricky.
Suppose for the moment that we can find a grammar whose variables are of
the form (q i Aq j ) and whose productions are such that
if and only if the npda erases A from the stack while reading v and going from
state q i to state q j . “Erasing” here means that A and its effects (i.e., all the
successive strings by which it is replaced) are removed from the stack, bringing
the symbol originally below A to the top. If we can find such a grammar, and if
we choose (q 0 zq f ) as its start symbol, then
if and only if the npda removes z (creating an empty stack) while reading w and
going from q 0 to q f . But this is exactly how the npda accepts w. Therefore, the
language generated by the grammar will be identical to the language accepted by
the npda.
To construct a grammar that satisfies these conditions, we examine the
different types of transitions that can be made by the npda. Since (7.5) involves
an immediate erasure of A, the grammar will have a corresponding production
Productions of type (7.6) generate the set of rules
where q k and q l take on all possible values in Q. This is due to the fact that to
erase A we first replace it with BC, while reading an a and going from state qi to
shown that for any npda there exists an equivalent one having properties 1 and 2.
This equivalence is explored partially in Exercises 16 and 17 in Section 7.1.
Here we need to explore it further, but again we will leave the arguments as an
exercise (see Exercise 16 at the end of this section). Taking this as given, we
now construct a context-free grammar for the language accepted by the npda.
As stated, we want the sentential form to represent the content of the stack.
But the configuration of the npda also involves an internal state, and this has to
be remembered in the sentential form as well. It is hard to see how this can be
done, and the construction we give here is a little tricky.
Suppose for the moment that we can find a grammar whose variables are of
the form (q i Aq j ) and whose productions are such that
if and only if the npda erases A from the stack while reading v and going from
state q i to state q j . “Erasing” here means that A and its effects (i.e., all the
successive strings by which it is replaced) are removed from the stack, bringing
the symbol originally below A to the top. If we can find such a grammar, and if
we choose (q 0 zq f ) as its start symbol, then
if and only if the npda removes z (creating an empty stack) while reading w and
going from q 0 to q f . But this is exactly how the npda accepts w. Therefore, the
language generated by the grammar will be identical to the language accepted by
the npda.
To construct a grammar that satisfies these conditions, we examine the
different types of transitions that can be made by the npda. Since (7.5) involves
an immediate erasure of A, the grammar will have a corresponding production
Productions of type (7.6) generate the set of rules
where q k and q l take on all possible values in Q. This is due to the fact that to
erase A we first replace it with BC, while reading an a and going from state qi to