To recognize string w, begin with the instantaneous assumption
( , , )
q w z
0
where
q 0 = start state
w = entire string to be pro cessed, and
z = start stack sym bol.
Starting with this instantaneous description, make zero or more moves,
just as is done with an NFA.
There are two kinds of moves that can be made:
(a) λ-Transitions: If you are in state q 1 , x is the top (leftmost) symbol
in the stack, and
δ
λ
( , , ) {( , ),
}
q
x
q w
1
2
2
=
KK
then you can replace the symbol x with the string w 2 and move to q 2 .
(b) Nonempty transitions: If you are in the state q 1 , ‘a’ is the next
unconsumed input symbol, x is the top (leftmost) symbol in the
stack, and
δ( , , ) {( , ),
}
q a x
q w
1
2
2
=
KK
then you can remove the ‘a’ from the input string, replace the
symbol x with the string w 2 , and move to state q 2 .
If you are in the final state when you reach the end of the string (and may
be make some λ-transition after reaching the end), then the string is accepted
by the NPDA. It does not matter what is on the stack.
3.1.6 An Exam ple of NPDA Exe cu tion
Let us consider the NPDA given by
δ
λ
δ
λ
λ
δ
( , , ) {( , ), ( , )}
( , , ) {( , )}
( ,
q a
q
q
q
q
q a
0
1
3
0
3
1
0
10
0
=
=
, ) {( , )}
( , , ) {( , )}
( , , ) {( , )}
1
11
1
1
1
1
2
2
2
=
=
=
q
q b
q
q b
q
δ
λ
δ
λ
δ( , , ) {( , )}
q
q
1
3
0
λ
λ
=
It is possible for us to recognize the string “aaabbb” using the following
sequence of “Moves”:
( ,
, ) |– ( ,
, )
|– ( ,
,
)
|– ( ,
q aaabbb
q aabbb
q abbb
q b
0
1
1
1
0
10
110
bb
q bb
q b
q
,
)
|– ( , ,
)
|– ( , , )
|– ( , , )
1110
110
10
0
2
2
2 λ
Pushdown Automata
163