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.
There may also be a λ-transition, where the second argument may be λ,
which means that a move that does not consume an input symbol is possible.
No move is possible if the stack is empty.
Example: Consider the set of transition rules of an NPDA given by
δ
λ
( , , ) {( , ), ( , )}
q a b
q cd q
1
2
3
=
If at any time the control unit is in state q 1 , 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:
(a) The control unit tends to go into the state q 2 and the string ‘cd’
replaces ‘b’ on top of the stack.
(b) The control unit goes into state q 3 with the symbol b removed from
the top of the stack.
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. As we are dealing with nondeterministic pushdown automaton, the
result of applying δ is a finite set of (q, x) pairs.
3.1.3 Draw ing 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 Σ, we can label arcs with
a x y
| , where a
x
∈
∈
Σ
Γ
,
and y ∈Γ
* .
Let us consider the NPDA given by
(
{ , , , },
{ , },
{ , }, , ,
,
{ })
Q q q q q
a b
q Z
F
q
=
=
=
=
=
0
1
2
3
0
3
0 1
0
Σ
Γ
δ
where
δ
λ
δ
λ
λ
δ
( , , ) {( , ), ( , )}
( , , ) {( , )}
( ,
q a
q
q
q
q
q a
0
1
3
0
3
1
0
10
0
=
=
, ) {( , )}
( , , ) {( , )}
( , , ) {( , )}
1
11
1
1
1
1
2
1
2
=
=
=
q
q b
q
q b
q
δ
λ
δ
λ
δ( , , ) {( , )}
q
q
2
3
0
λ
λ
=
Pushdown Automata
161