Re: Grammar for a^n b^m c^n a^m

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

Return to the comp.compilers page.
Search the comp.compilers archives again.