the pumping lemma for regular languages
The pumping lemma is the pigeonhole principle wearing a disguise. A DFA has only finitely many states, so when it reads a long enough string it must visit some state TWICE — like walking a hallway with fewer doors than steps, you are bound to pass through one door again. The path between those two visits is a loop, and a loop can be walked zero times, once, or a hundred times. Every regular language must therefore tolerate that looping: a long string in it has a middle chunk you can repeat ('pump') freely and stay in the language.
The precise statement: for every regular language L there is a number p (the pumping length) such that every string w in L with length at least p can be split into three pieces w = xyz satisfying three conditions: (1) |y| ≥ 1 (the middle piece y is non-empty), (2) |xy| ≤ p (x and y together fit within the first p symbols), and (3) for every i ≥ 0, the pumped string x y^i z is also in L (so xz, xyz, xyyz, xyyyz, ... are all in L). Here y is the loop the automaton was forced to enter, and repeating y i times corresponds to going around that loop i times.
Read the lemma carefully: it is a guarantee ABOUT regular languages, and we use its CONTRAPOSITIVE to prove a language is NOT regular. It says nothing about how to recognize a language and it is a one-way door — passing the pumping condition does not make a language regular. Its honest job is narrow but powerful: it certifies the unavoidable repetition that finite memory forces.
In a DFA with 3 states reading aaaa, by the pigeonhole principle two of the visited states coincide; the symbols read between those two visits form a loop y. So aaaa = x y z, and x y^i z (...aa..., aaaa, aaaaa with extra y's) all end in the same state — all accepted or all rejected together.
A long enough run revisits a state; the symbols in between are a pumpable loop.
The lemma is NECESSARY but NOT SUFFICIENT: every regular language satisfies it, but some NON-regular languages satisfy it too. So you can prove non-regularity by violating it, but you can NEVER prove regularity by checking it.