Theorem 7.1
For any context-free language L, there exists an npda M such that
L = L (M).
Proof: If L is a λ-free context-free language, there exists a context-free grammar
in Greibach normal form for it. Let G = (V, T, S, P) be such a grammar. We then
construct an npda that simulates leftmost derivations in this grammar. As
suggested, the simulation will be done so that the unprocessed part of the
sentential form is in the stack, while the terminal prefix of any sentential form
matches the corresponding prefix of the input string.
Specifically, the npda will be
where z ∉ V. Note that the input alphabet of M is identical with the set of
terminals of G and that the stack alphabet contains the set of variables of the
grammar.
The transition function will include
so that after the first move of M, the stack contains the start symbol S of the
derivation. (The stack start symbol z is a marker to allow us to detect the end of
the derivation.) In addition, the set of transition rules is such that
whenever
A → au
is in P. This reads input a and removes the variable A from the stack, replacing it
with u. In this way it generates the transitions that allow the pda tosimulate all
derivations. Finally, we have
to get M into a final state.