Drawtomata / Pumping lemma for regular languages
Pumping lemma for regular languages
Pick a language such as aⁿbⁿ above. Drawtomata lists every way to split w into xyz with |xy| ≤ p and |y| ≥ 1, and the i for which xyⁱz leaves the language, so you can see why the language is not regular.
The lemma
If L is regular, there is a p ≥ 1 such that every w in L with |w| ≥ p can be written w = xyz with |xy| ≤ p and |y| ≥ 1, and xyⁱz is in L for every i ≥ 0.
Using it as a game
- The adversary picks p.
- You pick a string w in L with |w| ≥ p. The choice matters: for aⁿbⁿ take w = aᵖbᵖ.
- The adversary picks any split w = xyz with |xy| ≤ p and |y| ≥ 1.
- You pick i so that xyⁱz is not in L. If you can do this for every split, L is not regular.
For aⁿbⁿ, y lies inside the first p symbols, so it holds only a’s. Pumping changes the number of a’s but not of b’s, and i = 0 already breaks every split.
Regular languages
Switch to the regular mode and type a regular expression to see the other side: p is the number of states of the minimal DFA, and the pigeonhole principle gives a split that always pumps.