next up previous
Next: e.g. Up: EQUIVALENCE OF CFL AND Previous:

If L is N(M) for some PDA M, then L is a CFL.

Proof:
Let tex2html_wrap_inline349
Contruct a CFG from M:
Variables are S and objects of the form [q, A, p] for tex2html_wrap_inline357 , and tex2html_wrap_inline359 .
Productions are:

  1. tex2html_wrap_inline361 , for each tex2html_wrap_inline363
  2. tex2html_wrap_inline365
    tex2html_wrap_inline367
for each tex2html_wrap_inline369
for each tex2html_wrap_inline371
for each tex2html_wrap_inline373
such that tex2html_wrap_inline375 contains tex2html_wrap_inline377 .

If tex2html_wrap_inline375 contains tex2html_wrap_inline381
then tex2html_wrap_inline383



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