the grammar was in Greibach normal form. It is not necessary to do this; we can
make a similar and only slightly more complicated construction from a general
context-free grammar. For example, for productions of the form we remove A
from the stack and replace it with Bx, but consume no input symbol. For
productions of the form
A → Bx,
A → abCx,
we must first match the ab in the input against a similar string in the stack and
then replace A with C x . We leave the details of the construction and the
associated proof as an exercise.
Context-Free Grammars for Pushdown Automata
The converse of Theorem 7.1 is also true. The construction involved readily
suggests itself: Reverse the process in Theorem 7.1 so that the grammar
simulates the moves of the pda. This means that the content of the stack should
be reflected in the variable part of the sentential form, while the processed input
is the terminal prefix of the sentential form. Quite a few details are needed to
make this work.
To keep the discussion as simple as possible, we will assume that the npda in
question meets the following requirements:
1. It has a single final state qf that is entered if and only if the stack is
empty;
2. With a ∈ Σ ∪ {λ}, all transitions must have the form δ(q i , a, A) = {c 1 ,
C 2 ,…, c n }, where
or
That is, each move either increases or decreases the stack content by a single
symbol.