From CFG to NPDA
For any context-free grammar in Greibach Normal Form
we can build an equivalent
nondeterministic pushdown automaton.
This establishes that an npda is at least as powerful
as a cfg.
Any string of a context-free language has a leftmost derivation.
We set up the npda so that the stack contents "correspond" to this
every move of the npda represents one derivation step.
The sentential form is:
- the characters already read,
- PLUS the symbols on the stack
- MINUS the final z (the initial stack symbol).
In the npda we will construct,
the states are hardly important at all.
All the real work is done on the stack.
In fact, we will use only the following three states,
regardless of the complexity of the grammar:
- Start state q0 just gets things initialized.
We use the transition from q0 to q1
to put the grammar's start symbol on the stack.
- State q1 does the bulk of the work.
We represent every derivation step as a move
from q1 to q1.
- We use the transition from q1 to
qf to accept the string.
Copyright © 1996 by David Matuszek
Last modified Mar 17, 1996