[Overview] [Previous]
[Next]
From NPDA to CFG, Part II
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 contents.
Variable names will have the form [qiAqj],
where qi and qj are states and A is a
variable.
The "meaning" of the variable [qiAqj]
is that the npda can go from state qi with Ax on the
stack to state qj with x on the stack.
Each transition
of the form 
(qi,
a, A) = (qj, 
)
results in a single grammar rule.
Each transition
of the form (qi,
a, A) = (qj, BC) results in a multitude of grammar rules, one for
each pair of states qx and qy in the npda.
This algorithm results in a lot of useless (unreachable)
productions,
but the useful productions define the context-free grammar
recognized by the npda.
Copyright © 1996 by David Matuszek
Last modified Mar 18, 1996