[Overview] [Previous] [Next]

Accepting Strings with an NPDA

Suppose you have the npda M = (Q,

, q₀, z, F).
How do you use this npda to recognize strings?

To recognize string w, begin with the instantaneous description

(q₀, w, z) where

q₀ is the start state,
w is the entire string to be processed, and
z is the start stack symbol.

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:

-transitions. If you are in state q₁, x is the top (leftmost) symbol in the stack, and (q₁, , x) = {(q₂, w₂), ...}, then you can replace the symbol x with the string w₂ and move to state q₂.
Nonempty transitions. If you are in state q₁, a is the next unconsumed input symbol, x is the top (leftmost) symbol in the stack, and (q₁, a, x) = {(q₂, w₂), ...}, then you can remove the a from the input string, replace the symbol x with the string w₂, and move to state q₂.

If you are in a final state when you reach the end of the string (and maybe make some

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.