This NPDA is drawn as follows.
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.’.
3.1.4 Exe cu tion of NPDA
Assume that someone is in the middle of stepping through a string with a DFA,
and we need to take over and finish the job. There are two things that are
required to be known:
(a) the state of the DFA is in, and
(b) what the remaining input is.
But if the automaton is an NPDA we need to know one more viz., contents
of the stack.
Instan ta neous Descrip tion of a PDA
The Instantaneous description of a PDA is a triplet (q, w, u),
where
q = cur rent state of the autom a ton
w = unread part of the input string
u = stack con tents (writ ten as a string, with the leftmost
sym bol at the top of the stack).
Let the symbol “ |–” denote a move of the NPDA, and suppose that
δ( , , ) {( , ), },
q a x
q y
1
2
=
K then the following is possible:
( ,
, ) |– ( , , )
q aW xz
q W yz
1
2
where W indicates the rest of the string following ‘a’ and Z indicates the rest of
the stack contents underneath the x.
This notation tells that in moving from state q 1 to state q 2 , an ‘a’ is
consumed from the input string aW, and the x at the top (left) of the stack xZ is
replaced with y, leaving yZ on the stack.
3.1.5 Accepting Strings with an NPDA
Assume that you have the NPDA given by
M
Q
q z F
= ( , , , , , , ).
Σ Γ δ 0
162
Theory of Automata, Formal Languages and Computation
q 0
q 1
q 3
q 2
a/1,11
b/1,λ
a/0,10
a/0,λ
λ/0,λ
λ/0,λ
b/1,λ