Way way off the beaten path here, but this is the best example of usage of the pumping lemma I've seen. Just need somewhere to put it...
The below is taken from here.
Theorem:
Let be a regular language, and be a string. Then there exists a constant s.t. .
We can break into three strings, , s.t.:
Method to prove that a language is not regular:
At first, we have to assume that is regular.
So, the pumping lemma should hold for .
Use the pumping lemma to obtain a contradiction:
Select s.t. .
Select s.t. .
Select s.t.
Assign the remaining string to .
Select s.t. the resulting string is not in .
Problem:
Prove that is not regular.
Solution:
At first, we assume that is regular and is the number of states.
Let . Thus .
By the pumping lemma, let , where .
Let , , and , where , , , . Thusly .
Let . Then .
Number of .
Hence, . Since , is not of the form !!!!!!!!!!!!!!!