Example 7.9
Consider the string w = aab. This is accepted by the pda in Example 7.8, with
successive configurations
The corresponding derivation with G is
The steps in the proof of the following theorem will be easier to understand
if you notice the correspondence between the successive instantaneous
descriptions of the pda and the sentential forms in the derivation. The first q i in
the leftmost variable of every sentential form is the current state of the pda,
while the sequence of middle symbols is the same as the stack content.
Although the construction yields a rather complicated grammar, it can be applied
to any pda whose transition rules satisfy the given conditions. This forms the
basis for the proof of the general result.
Theorem 7.2
If L = L (M) for some npda M, then L is a context-free language.
Proof: Assume that M = (Q, Σ, Γ, δ, q 0 , z, {q f }) satisfies conditions 1 and 2
above. We use the suggested construction to get the grammar G = (V, T, S, P),
with T = Σ and V consisting of elements of the form (q i cq j ). We will show that
the grammar so obtained is such that for all q i , q j , ∈ Q, A ∈ Γ, X ∈ Γ*, u, v ∈,