[Overview] [Previous] [Next]

Transition Functions for NPDAs

The transition function for an npda has the form
delta: Q cross product (sigma union {empty string}) cross product gamma goes to finite subsets of Q cross product gamma*

delta is now a function of three arguments. The first two are the same as before: the state, and either empty string 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 empty string rather than a member of the input alphabet (so that no input symbol is consumed), there is no such option for the third argument. delta always consumes a symbol from the stack; no move is possible if the stack is empty.

In the deterministic case, when the function delta is applied, the automaton moves to a new state qis a member ofQ and pushes a new string of symbols xis a member ofgamma* onto the stack. Since we are dealing with a nondeterministic pushdown automaton, the result of applying delta 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 delta for every possible combination of arguments. For any case where delta is not specified, the transition is to null setis a proper subset ofQ, the empty set of states.


Copyright 1996 by David Matuszek
Last modified Mar 3, 1996