next up previous
Next: Up: EQUIVALENCE OF CFL AND Previous: EQUIVALENCE OF CFL AND

If L is a CFL, then there exists a PDA M such that L = N(M)

Proof:
Let tex2html_wrap_inline259 is not in L(G).

Let G = (V, T, P, S), in GNF.

Construct tex2html_wrap_inline265 ,
where if tex2html_wrap_inline267 in P
then tex2html_wrap_inline271

We show that tex2html_wrap_inline273
tex2html_wrap_inline275 could be tex2html_wrap_inline259
tex2html_wrap_inline279
tex2html_wrap_inline281

Let tex2html_wrap_inline283
We show, by induction on i,
tex2html_wrap_inline287



Sushil Prasad
Tue Jul 21 15:15:53 EDT 1998