Pumping lemma for regular languages

From Wikipedia, the free encyclopedia

In the theory of formal languages, the pumping lemma for regular languages is a lemma that gives a property that all regular languages have. Its primary use is to prove a language is not regular.

1 Formal Statement
2 Use of Lemma
3 Proof of Lemma
4 Lemma not sufficient
5 General version of Pumping Lemma for Regular Languages
6 See also
7 References
8 External links

[edit] Formal Statement

If a language L is regular, then there exists a number p > 0 such that every string w in L with |w| ≥ p can be written in the following form, where p is a pumping length:

w = xyz

with strings x, y and z such that |xy| ≤ p, |y| > 0 and

xy ⁱ z is in L for every integer i ≥ 0.

[edit] Use of Lemma

When using this lemma to prove a language non-regular, it is generally done with a proof by contradiction. If we assume that a language L is regular, then the pumping lemma for regular languages must hold for all strings in L. By showing that there exists an instance where the lemma does not hold, we also show that our assumption is incorrect: L cannot be regular. This is done by finding a string w ∈ L and integer i where the pumping lemma does not hold.

Using this lemma, one can, for instance, prove that the language L = {aⁿbⁿ : n ≥ 0} over the alphabet Σ = {a, b} is not regular. We will let w, x, y, z, p, and i be as stated in the pumping lemma for regular languages. Let w = a^pb^p. It is obviously in L, and the pumping lemma therefore yields a decomposition of w = xyz with |xy| ≤ p, |y| ≥ 1 and xyⁱz in L for every i ≥ 0. Since the first p characters are all a's, we know that xy is in {a*}. Because |y| ≥ 1, it consists of a non-zero number of as, and xy²z has more as than bs and is therefore not in L (note that any value of i ≠ 1 will give us a contradiction). We have reached a contradiction because, in this case, the pumping lemma does not hold. Therefore, the assumption that L is regular must be incorrect. L is not regular.

The proof that the language of balanced (i.e. properly nested) parentheses is not regular follows the same idea. Given p, there is a string of balanced parentheses that begins with more than p left parentheses, so that y will consist entirely of left parentheses. By repeating y, we can produce a string that does not contain the same number of left and right parentheses, and so they cannot be balanced.

[edit] Proof of Lemma

The proof idea uses the fact that for every regular language there is a finite state machine (FSA) that accepts the language. If the regular language is finite, then the pumping lemma is trivially true since there are no strings in the language greater than the pumping length.

If the regular language is infinite, then there must be some minimal FSA that accepts the language. The number of states in this FSA are counted, and then, that count is used as the pumping length p. If the string's length is longer than p, then there must be at least one state that is repeated (which we will call state S). The transitions that take the machine from state S back to state S match some string. This string is called y in the lemma, and since the machine will match a string without the y portion, or the string y can be repeated, the conditions of the lemma are satisfied.

This makes more sense with an example. The following image shows an FSA.

The FSA accepts the string: abcbcd . Since this is longer than the number of states there are repeated states. In this example, the repeated states are states q1 and q2. Since the substring bcbc of string abcbcd takes the machine through transitions that start at state q1 and end at state q1, the string portion could be repeated and the FSA would still accept giving the string abcbcbcbcd, and the string portion could be removed and the FSA would still accept giving the string ad. In terms of the pumping lemma, the string abcbcd is broken into a x portion a, a y portion bc and a z portion bcd. (Note, it could be broken in different ways such as a x portion a , a y portion bcbc and a z portion d and all the conditions hold except that |xy| ≤ p)

[edit] Lemma not sufficient

Note that the pumping lemma does not give a sufficient condition for a language to be regular. That is, the lemma holds for some non-regular languages. If the lemma does not hold for a language L, then L is not regular. If the lemma does hold for a language L, L might be regular. For example, the language {uu^Rv : u,v $\in$ {0,1}⁺} (strings over the alphabet {0,1} consisting of a nonempty even palindrome followed by another nonempty string) is not regular but can still be "pumped" with p = 4: Suppose w=uu^Rv has length at least 4. If u has length 1, then |v| ≥ 2 and we can take y to be the first character in v. Otherwise, take y to be the first character of u and note that y^k for k ≥ 2 starts with the nonempty palindrome yy. For a practical test that exactly characterizes regular languages, see the Myhill-Nerode theorem. The typical method for proving that a language is regular is to construct either a Finite State Machine or a Regular Expression for the language.

[edit] General version of Pumping Lemma for Regular Languages

If a language L is regular, then there exists a number p > 0 such that every string uwv in L with |w| ≥ p can be written in the form; where p is a pumping length.

uwv = uxyzv

with strings x, y and z such that |xy| ≤ p, |y| > 0 and

uxyⁱzv is in L for every integer i ≥ 0.

This version can be used to prove many more languages are non-regular, since it imposes stricter requirements on the language.