Pumping Lemma for Regular Languages

The standard tool for proving a language is not regular.

The idea

Lemma (Pumping lemma).

If $L$ is regular, there is a pumping length $p$ such that every string $s \in L$ with $|s| \ge p$ can be written $s = xyz$ with $|y| > 0, \qquad |xy| \le p, \qquad xy^{i}z \in L \ \text{ for every } i \ge 0.$

The lemma comes from counting states. Let a DFA with $p$ states recognize $L$, and run it on a string $s \in L$ with $|s| \ge p$. Over the first $p$ symbols the machine occupies $p + 1$ states, so it visits some state twice. Take $y$ to be the input read between those two visits, $x$ what came before, and $z$ the rest. Reading $y$ returns the machine to the state where $y$ began, so it ends in the same accepting state whether it traverses that loop once, many times, or not at all. Hence every $xy^{i}z$ lies in $L$; and by construction $y$ is nonempty and falls within the first $p$ symbols.

The lemma is used in the contrapositive. Every regular language has the pumping property, but so do some nonregular languages, so verifying the property proves nothing. To prove $L$ is not regular, suppose a pumping length $p$ existed, choose one string $s \in L$ with $|s| \ge p$, and show that every split obeying $|y| > 0$ and $|xy| \le p$ has some $i$ with $xy^{i}z \notin L$. You choose $s$ and $i$; the argument must defeat every split.

Ways to work on it

• Walkthrough. State the pumping lemma and use it to prove a first language is not regular.
• Practice. Choose a witness and pump to break a balance condition.
• Hardest. Prove the language of unary primes is not regular.

Not sure where to start? Take the ten-question placement test.