Pumping Lemma for Regular Languages

The pumping lemma for regular languages is a property that all regular languages must satisfy, used primarily to prove that certain languages are not regular. The lemma states that for any regular language L, there exists a constant p (the pumping length) such that any string s in L with length at least p can be divided into three parts s = xyz where |y| > 0, |xy| ≤ p, and xy^iz is in L for all integers i ≥ 0. This means that sufficiently long strings in a regular language must contain a repeatable segment — a structural constraint that arises directly from the finiteness of the recognizing automaton's state set. The pumping lemma is a negative tool: it cannot prove regularity, but it can disprove it by showing that a language violates the property. Its most famous application is proving that the language {a^n b^n | n ≥ 0} is not regular, since any division of a sufficiently long string would force the pumped region to contain only a's, unbalancing the count. The lemma is one of a family of pumping lemmas that characterize different language classes, including the more complex pumping lemma for context-free languages.