: Q 
(
{
})
finite subsets of Q
*
: Q
(
{})
finite subsets of Q
*
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 q
Q
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.