Context-Free Pumping Lemma

Let be a Formal Language
We say satisfies the
context free pumping lemma with pumping number
if for every word with
there are words such that:

• for all we have:

Theorem

For every Context-Free Formal Language
there is a number
such that satisfies the context free pumping lemma
with pumping number .

Proof (sketch)

WLOG generating is in Chomsky Normal Form.
Let and .
We claim is the pumping number of .
Let be a word with
Note that the height of the Parse Tree of is at least .
So find the terminal node whose path from is at least .
Then find on that path such that path from to is exactly .
Then there is a repeated variable in between and ,
say it repeats at times and .
Let be the subtree of .
We can insert at as many times as we want
and we proved the theorem.