Pumping lemma for regular languages

Remarks

Take a DFA for $L$ and let $p$ be its number of states. While reading the first $p$ letters of $w$, the automaton visits $p + 1$ states, so by the pigeonhole principle some state repeats. Let $y$ be the nonempty piece read between the two visits; this loop can be skipped or repeated any number of times without changing the final state. Example of use: suppose $\set{a^n b^n : n \ge 0}$ were regular with constant $p$, and take $w = a^p b^p$. By clause 2 the piece $y$ lies inside the $a$'s, so $x y^2 z$ has more $a$'s than $b$'s, which is a contradiction. The converse fails: there are non-regular languages that satisfy the conclusion, so the lemma can only show that a language is not regular.

Going deeper

For a student

The lemma is the usual first tool for proving that a language is not regular. One assumes regularity and picks a clever word of length at least $p$. Then one shows that every allowed split leads to a pumped word outside the language. It is often combined with closure properties to reduce a hard case to a known one. Since the condition is only necessary, the Myhill–Nerode theorem, which gives a characterization, is needed in some cases. A similar pumping lemma holds for context-free languages, with two pumped pieces.