is now a function
of three arguments. The first two are the same as before: the state, and either
or a
symbol from the input alphabet. The third argument is *the symbol on top
of the stack.* Just as the input symbol is "consumed" when the
function is applied, the stack symbol is also "consumed" (removed
from the stack).

Note that while the second argument may be rather than a member of the input alphabet (so that no input symbol is consumed), there is no such option for the third argument. always consumes a symbol from the stack; no move is possible if the stack is empty.

In the deterministic case, when the function is applied, the automaton moves to a new state qQ and pushes a new string of symbols x* onto the stack. Since we are dealing with a nondeterministic pushdown automaton, the result of applying is a finite set of (q, x) pairs. If we were to draw the automaton, each such pair would be represented by a single arc.

As with an nfa, we do not need to specify for every possible combination of arguments. For any case where is not specified, the transition is to Q, the empty set of states.

Copyright © 1996 by David Matuszek

Last modified Mar 3, 1996