[Overview] [Previous] [Next]

From NPDA to CFG, Part I

We have shown that, for any cfg, we can produce an equivalent ndfa. We will now show that, for any ndfa, we can produce an equivalent cfg. This will establish the equivalence of cfgs and ndfas.

We assert without proof that any npda can be transformed into an equivalent npda that has the following form:


Copyright 1996 by David Matuszek
Last modified Mar 18, 1996