Transition Functions for NPDA: The transition function for an NPDA has the form
d : Q ´ (Σ ∪ {λ}) ´ Γ -> Finite sub sets of Q X Γ
d is now a function of three arguments.
The first two arguments are the same as before:
Example: Consider the set of transition rules of an NPDA given by
d (q1 , a, b)={(q2 , cd), (q3 , l)}
If at any time the control unit is in state q1, the input symbol read is ‘a’, and the symbol on the top of stack is ‘b’, then one of the following two cases can occur:
In the deterministic case, when the function d is applied, the automaton moves to a new state q ÎQ and pushes a new string of symbols x ÎG* onto the stack. As we are dealing with non-deterministic pushdown automaton, the result of applying d is a finite set of (q, x) pairs.
Drawing NPDAs
NPDAs are not usually drawn. However, with a few minor extensions, we can draw an NPDA similar to the way we draw an NFA.
Instead of labeling an are with an element of S, we can label arcs with
a | x, y where a ÎS, x ÎG and yÎG* .
Let us consider the NPDA given by
Please note that the top of the stack is considered to be the left, so that, for example, if we get an ‘a’ from the starting position, the stack changes from ‘0’ to ‘10.’.