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

Timon Christl <christl@male.fmi.uni-passau.de>
19 Mar 2002 16:14:09 -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: Timon Christl <christl@male.fmi.uni-passau.de>
Newsgroups: comp.compilers
Date: 19 Mar 2002 16:14:09 -0500
Organization: Compilers Central
References: 02-03-089
Keywords: parse, theory
Posted-Date: 19 Mar 2002 16:14:09 EST

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).


--
Timon Christl <christl@fmi.uni-passau.de>


Post a followup to this message

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