[Overview] [Previous] [Next]

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.

Key idea: Any string of a context-free language has a leftmost derivation. We set up the npda so that the stack contents "correspond" to this sentential form; every move of the npda represents one derivation step.

abba [ABz] The sentential form is:

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:

Copyright 1996 by David Matuszek
Last modified Mar 17, 1996