# why does ${a^nb^n}$ fit the pumping lemma for context-free languages?

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 \land |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?

• contextfree rule for building this grammar: <S> = a<S>b
– Sim
Oct 10 '13 at 20:01
• yes I know that but I just wanted to see that this language satisfies the conditions of the pumping lemma. @Sim Oct 10 '13 at 20:02

This language satisfies the conditions of the Pumping lemma. (By the way, your question title is wrong: you are not asking why it is context-free; you are asking why it satisfies the conditions of the lemma, which it does.)

Take the string s=a^mb^m and assume m>0. Don't use p or n, otherwise it is confusing, because those letters are used in the lemma. Now let v="a", y="b", x="", u=a^(m-1), z=b^(m-1).

You can definitely pump it as much as you want. In other words, you take a string such as aaaaaabbbbb, then you pick the two middle letters: aaaa ab bbbb. Then you pump them: aaaa aaabbb bbbb. Still in the language.

• Thank you for your answer but if I pump up aaaabbbb, while string is middle ab, first pumping produces "aaaa abab aaaa" and it is out of order now. @Sergey Orshanskiy Oct 10 '13 at 20:23
• No, because the $\def\a{{\mathtt a}}\def\b{{\mathtt b}}\a$ part of the $\a\b$ is in string $v$, and the $\b$ part is in string $y$, and in between is the string $x$, which is empty. $v$ and $y$ get pumped separately, so pumping $\a\b$ gives us $\a^n\b^n$, not $(\a\b)^n$. Oct 10 '13 at 20:49
• Note: you can use LaTeX math in posts and comments, just type $...$.
– Raphael
Oct 11 '13 at 7:31
• Sergey , i think that its not enough just to find few cases that you cant pump the string...for ANY choice of v ,x and y you have to show that you cant pump the string...so in our case like Mark mentioned there is a choice of v,x,y that you can pump it (v=a,y=b,x="") so game over...
– user21619
Sep 10 '14 at 13:02