title: "Pumping Lemma"

Pumping Lemma

Definition. The pumping lemma states that for every regular language $A$ there exists a pumping length $p \geq 1$ such that every $s \in A$ with $|s| \geq p$ can be written $s = xyz$ where $xy^iz \in A$ for every $i \geq 0$, $|y| > 0$, and $|xy| \leq p$.

The proof, in Lecture 4, is the pigeonhole principle applied to the states a DFA visits while reading $s$: among the first $p+1$ of them two must coincide, and the loop between them is $y$. The lemma is used through its contrapositive, to prove a language is not regular, and the quantifiers decide who chooses what: $p$ and the split $xyz$ are given to you, while $s$ and $i$ are yours to choose. The converse fails, so a language having a pumping length does not make it regular.