The pumping lemma for regular languages is a fundamental result in automata theory. It is primarily used to prove that a given language is not regular by demonstrating that all regular languages must satisfy a particular “pumping” property.
Formal Statement
Let L be a regular language. Then there exists an integer p (known as the pumping length) such that every string s in L with length |s| ≥ p can be decomposed into three substrings, s = xyz, satisfying:
-
Length Condition: |xy| ≤ p
The first part of the string (x concatenated with y) is not longer than p. -
Non-Empty y: |y| > 0
The substring y must be non-empty (ensuring that something is being “pumped”). -
Pumping Condition: For all integers i ≥ 0, the string x y^i z is in L
Repeating y any number of times (including 0 times) results in a string that still belongs to L.
Explanation of the Conditions
-
Length Condition (|xy| ≤ p):
This condition guarantees that the loop (or repetition) captured by y occurs within the first p characters of the string. Since a finite automaton recognizing a regular language has a finite number of states, this ensures that a repetition must occur when processing a long enough string. -
Non-Empty y (|y| > 0):
This prevents the trivial decomposition where y is empty. An empty y would make the pumping condition vacuous since nothing would be repeated. -
Pumping Condition (x y^i z ∈ L for all i ≥ 0):
This is the crux of the lemma. It asserts that the string y can be “pumped” (repeated any number of times) and the resultant string will still belong to the language L.
How to Use the Pumping Lemma
The pumping lemma is most often used in proofs by contradiction to show that a language is not regular:
-
Assume:
Suppose L is regular. Then there exists a pumping length p. -
Select a String:
Choose a string s ∈ L such that |s| ≥ p. The choice of s is critical and is typically tailored to the structure of L. -
Decompose s:
For every possible decomposition of s into x, y, and z that satisfies |xy| ≤ p and |y| > 0, analyze the effect of “pumping” y. -
Reach a Contradiction:
Find an integer i (often i = 0 or i > 1) such that the string x y^i z does not belong to L. This contradicts the pumping lemma’s assertion, hence L must be non-regular.
Example: Non-Regular Language
Consider the language:
L = { a^n b^n | n ≥ 0 }
Proof Outline:
-
Assumption:
Assume L is regular, and let p be its pumping length. -
Choose s:
Let s = a^p b^p, so |s| = 2p ≥ p. -
Decompose s:
Since |xy| ≤ p, both x and y consist only of a’s. Let y = a^k, where k > 0. -
Pump y:
For i = 0, we get xz = a^(p-k) b^p. This string has fewer a’s than b’s and thus is not in L. -
Conclusion:
The contradiction implies that L is not regular.
Limitations
-
Necessity but Not Sufficiency:
While the pumping lemma must hold for all regular languages, there exist some non-regular languages that can, under certain decompositions, seem to satisfy the lemma. Therefore, the lemma is a necessary condition for regularity but not a sufficient condition. -
Dependence on s:
The effectiveness of the pumping lemma in proofs hinges on a clever choice of the string s. A poor choice might not reveal the non-regularity of the language.
Conclusion
The pumping lemma is a powerful tool for understanding the properties of regular languages and proving non-regularity. Its strategic use in proofs can demonstrate inherent limitations in the computational power of finite automata.
For further reading, see standard texts such as “Introduction to the Theory of Computation” by Michael Sipser or “Automata Theory, Languages, and Computation” by Hopcroft, Motwani, and Ullman.