**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.

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 q
_{0}just gets things initialized. We use the transition from q_{0}to q_{1}to put the grammar's start symbol on the stack.(q _{0}, , z) {(q_{1}, Sz)} - State q
_{1}does the bulk of the work. We represent every derivation step as a move from q_{1}to q_{1}. - We use the transition from q
_{1}to q_{f}to accept the string.(q _{1}, , z) {(q_{f}, z)}

Copyright © 1996 by David Matuszek

Last modified Mar 17, 1996