next up previous contents
Next: The Pumping Lemma: Examples Up: Proving that a Language Previous: Proving that a Language   Contents

The Pumping Lemma for context-free languages

For any context-free grammar $G$, there is a number $K$, depending on $G$, such that any string generated by $G$ which has length greater than $K$ can be written in the form $uvxyz$, so that either $v$ or $y$ is non-empty, and $uv^nxy^nz$ is in the language generated by $G$ for all $n \geq 0$.
Proof:
Based on the above discussion, we can see that the number $K$ is simply $p^m$.
${\cal QED}$



James Power 2002-11-29