|Grammar for a^n b^m c^n a^m firstname.lastname@example.org (Gioele) (2002-03-17)|
|Re: Grammar for a^n b^m c^n a^m email@example.com (ANDREI Stefan) (2002-03-19)|
|Re: Grammar for a^n b^m c^n a^m firstname.lastname@example.org (Timon Christl) (2002-03-19)|
|Re: Grammar for a^n b^m c^n a^m email@example.com (Mikael 'Zayenz' Lagerkvist) (2002-03-21)|
|From:||"Mikael 'Zayenz' Lagerkvist" <firstname.lastname@example.org>|
|Date:||21 Mar 2002 21:54:59 -0500|
|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
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
Royal Institute of Technology (KTH)
Return to the
Search the comp.compilers archives again.