[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 delta(qi, a, A) = (qj, empty string) results in a single grammar rule.

Each transition of the form delta(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