why is $a^nb^n$ context-free?

Question

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?

Answer 1

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$.

Answer 2

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:

1. $|vxy| ≤ p$,
2. $|vy| ≥ 1$, and
3. $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:

1. You give the adversary $A$ your claimed pumping constant $p$ for this language. In this case it turns out that $p=3$ works.
2. $A$ picks $s$ with $|s| \ge p$. Let's say $A$ picks $s = \a^3\b^3$.
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.)
4. 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} $$