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?
Best Answer
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$.