Pumping Lemma for Regular Languages
A regular language is a language that can be expressed using a regular expression.
The pumping lemma for regular languages can be used to show that a language is not regular.
Theorem:
Let L be a regular language.
There is an integer p ≥ 1
such that any string w ∈ L with |w| ≥ p
can be rewritten as w = xyz such that y ≠ ε, |xy| ≤ p,
and xyiz ∈ L for each i ≥ 0.
The five parts of this theorem can be restated in the following way:
(1) for each regular language L,
(2) there exists a p ≥ 1, such that
(3) for each string w ∈ L with |w| ≥ p,
(4) there exist strings x, y, z with w = xyz, y ≠ ε, and |xy| ≤ p, such that
(5) for each i ≥ 0, xyiz ∈ L.
Example: L = { aibi : i ≥ 0 }
- By (1), we begin by assuming that L is regular. This assumption means that it must be possible to satisfy (2)-(5).
- (2) says that if L is regular, then we must be able to find find a p for which (3)-(5) are satisfied. We will show that no matter what p is chosen, the conditions of (3)-(5) will not be satisfied.
-
For every p ≥ 1, we can build a string w ∈ L with |w| ≥ p in the form of w = apbp.
In these cases, |w| = 2p, which always satisfies |w| ≥ p as required by (3). Therefore, (4)-(5) should always be possible to satisfy for this w.
-
Since the factors x and y must satisfy |xy| ≤ p and the first p symbols of w are all a, it must be that y = ak where 0 < k ≤ p.
It follows that x = aj with k + j ≤ p and z = ap - k - jbp. This factoring of w = xyz satisfies (4).
There must then exist a k and j for which (5) is satisfied.
-
No matter what choice of k and j is made, setting i = 0 generates the string xz = ajbp.
Since j < p, this string is not in L. Therefore, we cannot satisfy (5), which means we have found a contradiction.
This shows that no matter what p is chosen in (2), it will always be impossible to satisfy the requirements of (4)-(5) for some string that satisfies the requirements of (3).
Therefore, L is not a regular language. ■
References
back