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

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>

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