Pumping Lemma for Regular Languages

Abstract

The Pumping Lemma provides a necessary condition for a language to be regular. It is primarily used to prove that a language is non-regular via proof by contradiction.

Theorem

Let $L$ be a regular language. There exists an integer $p\ge 1$, called the pumping length, such that any string $s\in L$ with length $|s|\ge p$ can be split into three parts, $s=xyz$, satisfying:

1. For all $n\ge 0$, $x{y}^{n}z\in L$
2. $|y|>0$
3. $|xy|\le p$

Proof

For a regular language $L$, there exists a deterministic finite automaton (DFA) $M$ such that $L(M)=L$. Let $p$ be the number of states in $M$. If $s\in L$ and $|s|\ge p$, the sequence of states visited by $M$ during the computation of $s$ must contain at least $p+1$ states. By the Pigeonhole Principle, at least one state must be repeated within the first $p$ transitions. The substring $y$ corresponds to the path between the first and second occurrence of this repeated state.

Application

To prove $L$ is not regular:

1. Assume $L$ is regular.
2. Let $p$ be the pumping length.
3. Choose a specific string $s\in L$ such that $|s|\ge p$.
4. Consider all possible decompositions $s=xyz$ such that $|y|>0$ and $|xy|\le p$.
5. Find an $n\ge 0$ such that $x{y}^{n}z\notin L$, reaching a contradiction.

References

• Sipser, M. (2012). Introduction to the Theory of Computation.
• Hopcroft, J. E., Motwani, R., & Ullman, J. D. (2006). Introduction to Automata Theory, Languages, and Computation.