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

"Mikael 'Zayenz' Lagerkvist" <d00-mla@nada.kth.se>
21 Mar 2002 21:54:59 -0500

          From comp.compilers

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)
| List of all articles for this month |

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.