Failure of context-free pumping lemma of $a^nb^n$

computer sciencecontext-free-grammarpumping-lemma

I know $a^nb^n$ with $n\geq0$ is considered a context-free language, but if I try:

Using pumping length $p = 3$

$n = p$, thus we have $aaabbb$

$u =aa$ and $y = bb$

$v = a$, $w = b$ and $x=λ$, then $|vwx|=2\leq p=3$ and $|vx| = 1 \geq 1$

$uv^iwx^iy \notin L$, for instance, with $i=2$ we have:
$$aaaabbb$$

I know I'm wrong in some part of the process, that's I'm attempting to 'break' the lemma, to fully understand it.

Best Answer

Good question! The pumping lemma has a complicated statement, so it's helpful to understand what it means intuitively. Very roughly, the pumping lemma says:

Pumping lemma (context-free languages). If a language $L$ is context-free, then all sufficiently long strings in the language can be pumped—and, when you pump the string, the result will always belong to $L$.

In more detail, the pumping lemma says that if $L$ is a context free language then:

  1. The language $L$ has a specific number $p$ such that all strings longer than $p$ are "sufficiently long".
  2. For every sufficiently long string in $L$, there exists a proper way to decompose it into the form $\mathsf{uvwxy}$ such that certain constraints on $\mathsf{u,v,w,x,y}$ are satisfied.
  3. For any sufficiently long string in $L$, if you decompose it into the form $\mathsf{uvwxy}$ in just the right way, the pumped strings $\mathsf{uv}^k\mathsf{wx}^k\mathsf{y}$ will always belong to $L$ for every $k\geq 0$.

Usually to prove that a langauge is not context-free, you argue by contradiction. You say: suppose $L$ is context free. Then $p$ exists (1), and every sufficiently long string can be decomposed and pumped (2). But here is a carefully-constructed string I've built to satisfy (2). It belongs to the language $L$, and it's sufficiently long, but no matter how you decompose it, you can pump it to produce a string that isn't in $L$. This is impossible for context-free languages, therefore $L$ is not actually context free.

You are breaking part (1) of the lemma by choosing the value of $p$ yourself. You are breaking part (2) of the lemma by picking a specific decomposition yourself. The lemma says that every context-free language has its own pumping length $p$, and that all sufficiently long strings can be decomposed properly and pumped.

The pumping lemma says that strings are pumpable only when they're longer than the correct value of p for the language and only when they're decomposed in exactly the proper way for that specific string. It doesn't violate the pumping lemma if you pick your own value of $p$ and your own decomposition of the string and show that the result isn't pumpable.

Related Question