For example, the derivation
S
aAB
aaB
aabB
aabb
⇒
⇒
⇒
⇒
maps into the sequence of moves
( ,
, ) |– ( ,
, )
|– ( ,
,
)
|– ( , ,
q aabb z
q aabb Sz
q abb ABz
q bb Bz
0
1
1
1
)
|– ( , , )
|– ( , , )
|– ( , , )
q b Bz
q
z
q
1
1
2
λ
λ λ
3.2.4 NPDA to CFG
(a) We have shown that for any CFG, an equivalent NPDA can be obtained.
We shall show also that, for any NPDA, we can produce an equivalent CFG.
This will establish the equivalence of CFGs and NFDAs.
We shall assert without proof that any NPDA can be transformed into an
equivalent NPDA which has the following form:
(i) The NPDA has only one final state, which it enters if and only if
the stack is empty.
(ii) All transitions have the form
δ( , , ) { , , ,
}
q a A
c c c
= 1 2 3 KK
where each c i has one of the two forms
( , )
q j λ
or
( ,
)
q BC
j
(b) When we write a grammar, we can use any variable names we choose. As
in programming languages, we like to use “meaningful” variable names.
When we translate an NPDA into a CFG, we will use variable names that
encode information about both the state of the NPDA and the stack content
variable names will have the form
[
],
q Aq
i
j
where q i and q j are states and A is a variable.
The “meaning” of the variable [q i Aq j ] is that the NPDA can go from state
q i with Ax on the stack to state q j with x on the stack.
Each transition of the form δ
λ
( , , ) ( , )
q a A
q
i
j
=
results in a single
grammar rule.
Each transition of the form
δ( , , ) { ,
)
q a A
q BC
i
j
=
Pushdown Automata
169