[Overview] [Previous] [Next]

Accepting Strings with an NPDA

Suppose you have the npda M = (Q, sigma, gamma, delta, q0, z, F).
How do you use this npda to recognize strings?

To recognize string w, begin with the instantaneous description

(q0, w, z)
where Starting with this instantaneous description, make zero or more moves, just as you would with an nfa. There are two kinds of moves that you can make: If you are in a final state when you reach the end of the string (and maybe make some empty string transitions after reaching the end), then the string is accepted by the npda. It doesn't matter what is on the stack.

As usual with nondeterministic machines, the string is accepted if there is any way it could be accepted. If we take the "oracle" viewpoint, then every time we have to make a choice, we magically always make the right choice, so we will end in a final state if at all possible.


Copyright 1996 by David Matuszek
Last modified Mar 7, 1996