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

  1. The adversary picks p.
  2. You pick a string w in L with |w| ≥ p. The choice matters: for aⁿbⁿ take w = aᵖbᵖ.
  3. The adversary picks any split w = xyz with |xy| ≤ p and |y| ≥ 1.
  4. 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.