Not every language is regular. A finite automaton has finite memory, so it cannot count without bound — it cannot recognize { 0ⁿ1ⁿ }.
Definition · Pumping lemma
If A is regular, there is a length p (the pumping length) such that every string s ∈ A with |s| ≥ p can be split as s = xyz where:
- xyⁱz ∈ A for every i ≥ 0
- |y| > 0
- |xy| ≤ p
It only proves non-regularity
The pumping lemma is a necessary condition, not a sufficient one. We use its contrapositive: if pumping breaks membership, the language cannot be regular.