Pumping Lemma for Regular Sets

 
Figure 1: Paths from to .

Suppose n states in an FA.
If , with


If then for .

Pumping Lemma: Let L be a regular set. Then there is a constant n such that if z is any word in L, and , then we may write in such a way that , , and for all , is in L.

Furthermore, n is no greater than the number of states of the smallest FA accepting L.