Pumping Lemma for GFGs
If a derivation is long enough, some variable must appear twice on the same path in a parse tree (pigeon hole principle):
- This means that any sufficiently large derivation will have a middle part that can be repeated indefinitely.
Pumping in General
Consider that you have a CFG that accepts the following string with a production that repeats at least once.:
\[uvwxy\]We can make the production repeat more to create the following string:
\[uv^2wx^2y\]Without repeating the production, the following is valid under the same language:
\[uvy\]Pumping Example
Consider the following language, you’d like to know whether it is a CFG:
\[L=\{a^nb^nc^n:n\geq0\}\]If $L$ is a CFG then we should be able to split it into portions of $uv^nwx^ny$ and $uvy$.
This is not possible with this language no matter how it is split.
More examples of non-context free languages are given in the following lecture video.
Pumping Lemma for Context-Free Languages
For every context-free language $L$:
There exists a numver $n$ such that for every string $z$ in $L$ longer than $n$, we can write $z=uvwxy$ where:
- $\lvert vwx\rvert\leq n$
- $\lvert vx\rvert\geq 1$
- For every $i\geq0$, in the string $uv^iwx^iy$ is in the language $L$.
To prove that a language is not context-free we need to have one of two cases:
-
$v$ or $x$ contains two kinds of symbols:
\[a\underbrace{aa\ldots aa}_vbbb\ldots \underbrace{bbcc}_xc\ldots cc\]Then $uv^2wx^2y$ is not in $L$ because the pattern is wrong.
-
$v$ or $x$ contains one kind of symbol:
\[a\underbrace{aa\ldots }_vaabbb\ldots \underbrace{bb\ldots bb}_xc\ldots cc\]Then $uv^2wx^2y$ does not have the same number of $a$s $b$s and $c$s.