why is {a^nb^n} context-free?

1
votes

I am writing somthing about Ppumping Lemma. I know that the language L = { a^nb^n| n ≥ 0 } is context-free. But I don't understand how this language satisfies the conditions of pumping lemma (for context-free languages) ?

if we pick the string s = a^pb^p, |s| > p , |vxy| < p and |vy| > 0.

it seems it will be out of the language when we pump it (pump up or down) or there is something I'm missing.

Any explanation would help.

Edit: I am applying pumping lemma to a^nb^n and it fails to stay in the language for all cases. So, why is it Context free?

I just wanted to see that this language satisfies the conditions of the pumping lemma. But it seems it fails when I pump up s = uv^2xy^2z

2
context-free-grammarpumping-lemma
Yes, you missing something, That is you don't pump and genrate new string that should be in language, Read This-answer and this-answer – Grijesh Chauhan
This question appears to be off-topic because it belongs on math.stackexchange.com or on cs.stackexchange.com – Mihai Maruseac
they are for regular languages. thanks anyway. – user2226106
@user2226106 What do you means? Using pumping lemma you can proof that certain language is not regular (or not context free) but con't proof that language is regular or context free (depends which lemma you applies) Pumping lemma is Sufficient but not necessary condition. – Grijesh Chauhan

2 Answers

3
votes

Remember, you have to allow for any choice of v,x,y that satisfy the conditions. In particular, you can always pick 

u=a^{n-1}, v=a, x=empty, y=b, z=b^{n-1}.

Then vxy is short as desired, but pumping just gives you 

uv^kxy^kz = a^{n-1} a^k empty b^k b^{n-1} = a^{n+k-1} b^{n+k-1},

which is still in the language.

0
votes

For those wanting a layman explanation (reiterating what Grijesh wrote in the comments)..

Pumping Lemma is necessary but not sufficient.

What does this mean?

L1 = (a^n)(b^n)(c^n)

For L1, there is no way we can find u,v,x,y,z such that we could pump up/down and the string would be still in L1. Since L1 does not satisfy the Pumping Lemma, it fails the "necessary" part and we can surely say L1 is not Context Free.

But,

L2 = (a^n)(b^n)

For L2, there are some ways to choose u,v,x,y,z such that we could pump up/down and the string would be still in L2 (it also fails if we choose u,v,x,y,z in some other clever way). But since, Pumping Lemma is not sufficient, we cannot say whether L2 here is Context Free or not.

TLDR : Pumping Lemma can only say "No" for sure, it can not assuredly say "Yes".