[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:
- The npda has only one final state,
which it enters if and only if the stack is empty;
- All transitions have the form
(q, a, A) = {c1,
c2, c3, ...}
where each ci has one of the two forms
- (qj,
)
- (qj, BC)
Copyright © 1996 by David Matuszek
Last modified Mar 18, 1996