Pumping lemma for regular languages

In the theory of formal languages, the pumping lemma for regular languages describes an essential property of all regular languages. Informally, it says that all sufficiently long words in a regular language may be pumped - that is, have a middle section of the word repeated an arbitrary number of times - to produce a new word which also lies within the same language.

The pumping lemma was first articulated by Y. Bar-Hillel, M. Perles, E. Shamir in 1961.It is useful for disproving the regularity of a specific language in question. It is one of a few pumping lemmas, each with a similar purpose.

Formal statement

Let L be a regular language. Then there exists an integer p ≥ 1 depending only on L such that every string w in L of length at least p (p is called the "pumping length") can be written as w = xyz (i.e., w can be divided into three substrings), satisfying the following conditions:

1. |y| ≥ 1
2. |xy| ≤ p
3. for all i ≥ 0, xyiz ∈ L

y is the substring that can be pumped (removed or repeated any number of times, and the resulting string is always in L). (1) means the loop y to be pumped must be of length at least one; (2) means the loop must occur within the first p characters. There is no restriction on x and z.


Informal statement and explanation

The pumping lemma describes an essential property of regular languages. It says that a word w of the language L with length of at least m, (where m is a constant, called the pumping length, depending only on the language L) may be split into three substrings, w = xyz, such that the middle portion, y (which must not be empty), can be repeated an arbitrary number of times (including zero times, which removes it) yielding a string that is still in L. This process of repetition is known as "pumping". Moreover, the pumping lemma guarantees that the length of xy will be at most m, imposing a limit on the ways in which w may be split. Note that finite languages satisfy the pumping lemma trivially by having m equal to the maximum string length in L plus one.

Use of lemma

The pumping lemma is often used to prove that a particular language is non-regular: a proof by contradiction (of the language's regularity) may consist of exhibiting a word (of the required length) in the language which lacks the property outlined in the pumping lemma.

For example the language L = {anbn : n ≥ 0} over the alphabet Σ = {a, b} can be shown to be non-regular as follows. Let w, x, y, z, p, and i be as stated in the pumping lemma above. Let w in L be given by w = apbp. By the pumping lemma, there must be some decomposition w = xyz with |xy| ≤ p, |y| ≥ 1 such that xyiz in L for every i ≥ 0. If we let |xy|=p and |z|=p, then xy is the first half of w, consisting of p consecutive instances of the letter a. Because |y| ≥ 1, it contains at least one instance of the letter a and xy2z has more instances of the letter a than the letter b. Therefore xy2z is 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 pumped word does not belong to the language L. Therefore, the assumption that L is regular must be incorrect. Hence 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.
source: wikipidea