why is $a^nb^n$ context-free? 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?
 A: The thing is that the lemma only says that for a CFL $L$, a $p$ exists such that any string $s$ of length at least $p$ (i.e., $|s| \ge p$) can be decomposed as $s =uvwxy$ with $|vwx|<p$, $vx \neq \varepsilon$ and $uv^nwx^ny \in L$.
Now, in the example, consider $s=A^nB^n$. Take $p = 3$, $v=A$, $x=B$, $u=A^{n-1}$, $w=\varepsilon$ and $y=B^{n-1}$.
Then clearly $|vwx|=2<3$, $vx = AB \neq \varepsilon$ and $uv^mwx^my = A^{n-1}A^mB^mB^{n-1} = A^{m+n-1}B^{m+n-1} \in L$.
A: The pumping lemma for CFLs says that any sufficiently long string $s$ in a CFL $\mathcal L$ can be broken up into $s=uvxyz$ such that:


*

*$|vxy| ≤ p$,

*$|vy| ≥ 1$, and

*$uv^nxy^nz$ is in $\mathcal L$ for all $n ≥ 0$. 


$\def\a{{\tt a}}\def\b{{\tt b}}$
Let's suppose that your adversary $A$ claims that $\a^n\b^n$ is not a CFL, and you disagree.  The proof would go like this:


*

*You give the adversary $A$ your claimed pumping constant $p$ for this language.  In this case it turns out that $p=3$ works.

*$A$ picks $s$ with $|s| \ge p$.  Let's say $A$ picks $s = \a^3\b^3$.

*You pick $u,v,x,y,z$ as above, with $s = uvxyz$.  In this case you might choose $u = \a\a, v=\a, x=\epsilon, y=\b, $ and $z=\b\b$, as in Johannes Kloos's answer.  (Now we check to make sure these choices satisfy conditions  1, 2, and 3 of the previous paragraph.) 

*Now $A$ tries to  pick $m$ such that $uv^mxy^mz\notin\mathcal L$.  If $A$ can do this, you lose.  If $A$ can't, you win.


Clearly for this example, whatever $m$ is chosen by $A$ in step 4, you get $uv^mxy^mz = \a\a\; \a^m\; \epsilon\; \b^m\; \b\b = \a^{m+2}\b^{m+2}$ which is in $\mathcal L$, so $A$ loses, and $A$'s claim that $\mathcal L$ is not context-free fails.
Could $A$ have defeated you by making a better choice of $s$ back in step 2?  You should think about that.

The short answer to the question you asked is that $\a^n\b^n$ is a CFL because it is generated by the CFG:
$$\begin{align}
S & \to \a S\b \mid  \epsilon
\end{align}
$$
