21 Mar 2002 21:54:59 -0500

Related articles |
---|

Grammar for a^n b^m c^n a^m gstragli@tiscalinet.it (Gioele) (2002-03-17) |

Re: Grammar for a^n b^m c^n a^m stefan@infoiasi.ro (ANDREI Stefan) (2002-03-19) |

Re: Grammar for a^n b^m c^n a^m christl@male.fmi.uni-passau.de (Timon Christl) (2002-03-19) |

Re: Grammar for a^n b^m c^n a^m d00-mla@nada.kth.se (Mikael 'Zayenz' Lagerkvist) (2002-03-21) |

From: | "Mikael 'Zayenz' Lagerkvist" <d00-mla@nada.kth.se> |

Newsgroups: | comp.compilers |

Date: | 21 Mar 2002 21:54:59 -0500 |

Organization: | Compilers Central |

References: | 02-03-089 02-03-113 |

Keywords: | parse, theory |

Posted-Date: | 21 Mar 2002 21:54:59 EST |

Sorry to say, but your proof is incorrect.

The pumping lemma for contex-free grammars says that there exists a

string that can be written in the way that you describe. If this

lemma is to be used to disprove that a language is a CF language, one

can not choose the parts uvxyz freely, one must instead show that the

results hold for all possible choices of uvxyz.

In other words, the error is where you say "Lets choose...".

Hope this helps

Mikael Lagerkvist

On 19 Mar 2002, Timon Christl wrote:

*> On 17 Mar 2002 22:42:27 -0500, Gioele wrote*

*> > As Object .*

*> > Does a grammar for this language exist ? Is possible a type 2 Grammar?*

*>*

*> Lets use the pumping-lemma for context-free languages:*

*> Let L be a context-free language. Then for some k in N, every w in L*

*> with |w| >= k can be written as w = uvxyz where*

*>*

*> |v x y| <= k*

*> |v y| >= 1*

*> u v^n x y^n z is in L for all n>=0*

*>*

*> is true.*

*>*

*> If any of those properties is false the language cannot be a*

*> context-free language.*

*>*

*> Lets choose k = n+m and*

*> w = u v x y z*

*> u = a^n*

*> v = b^m*

*> x = <epsilon>*

*> y = c^n*

*> z = a^m.*

*>*

*> Then |w|>= k, |v x y| <= k and |v y| >=1, but the last requirement is*

*> not true:*

*>*

*> u v^N x y^N z = a^n (b^m)^N (c^n)^N a^m*

*>*

*> is not in L for _all_ N>=0. Let N=0, then u v^N x y^N z is a^b a^m,*

*> which is certainly not in L. Thus L cannot be a context-free language.*

*>*

*>*

*> (No warranty that this proof is correct. Please correct me if I'm wrong).*

___________________________________

Mikael 'Zayenz' Lagerkvist

Undergraduate Student

Computer Science

Royal Institute of Technology (KTH)

Stockholm, Sweden

Post a followup to this message

Return to the
comp.compilers page.

Search the
comp.compilers archives again.