Prev: TMFCS-10 Call for papers
Next: إلحقووووو حقيقه مش خيال إكسب لاب توب مجانى المقدم من شركة EZLapTop
From: stdazi on 21 Jan 2010 09:43
Hello!

I would like to prove that the language defined by L = { a^n b^(n*n) ;
n > 1 } is not context free.

Assuming L is context free and that n is the constant provided by the
pumping lemma we consider the word z = a^n b^(n*n).

We have to cover all possible partitions of z into z = uvwxy and show
that u v^i w x^i y is not in L for all i >= 0.

The first partition we may consider is the one such that vwx = a^k .
It is easy to show that for any such k v^i w x^i y is not in L for i =
0.

The second partition to consider is vwx = a^k b^l. And here I get
stuck. As far as I can see, there are many partitions of vwx into a^k
b^l. (v = eps, w = a^k , x = b^l ; v = a^k1, w = a^k2, x = a^(k-k1-
k2) b^l ; v = a^k1 b^l1, w = b^l2 , x = b^(l-l1-l2), etc...)

There seem to be many such partitions and I am kind of uncomfortable
checking them all. Is there any better way to be able to handle all
those partitions under one case?

At the classes we just covered the case v = a^k w = a^(k-k1) b^(l-l1)
x = b^l1 and assumed (??) this is the only case we have to cover for
vwx = a^k b^l - is this actually true?

Best regards,

J.

 | 
Pages: 1
Prev: TMFCS-10 Call for papers
Next: إلحقووووو حقيقه مش خيال إكسب لاب توب مجانى المقدم من شركة EZLapTop