Pumping Lemma

Pumping Lemma for Regular Languages

The language accepted by the finite automata is called Regular Language. If we are given a language L and asked whether it is regular or not? So, to prove a given Language L is not regular we use a method called Pumping Lemma.

The term Pumping Lemma is made up of two words:

1. Pumping: The word pumping refers to generate many input strings by pushing a symbol in an input string again and again.
2. Lemma:  The word Lemma refers to intermediate theorem in a proof.

Pumping Lemma is used to prove that given language is not regular. So, first of all we need to know when a language is called regular. A language is called regular if:

• Language is accepted by finite automata.
• A regular grammar can be constructed to exactly generate the strings in a language.
• A regular expression can be constructed to exactly generate the strings in a language.

Principle of Pumping Lemma

The pumping lemma states that all the regular languages have some special properties. If we can prove that the given language does not have those properties, then we can say that it is not a regular language.

Theorem 1: Pumping Lemma for Regular Languages

If L is an infinite regular language then there exists some positive integer n (pumping length) such that any string w ? L has length greater than or equal to n. i.e. |w| >=n, then string can be divided into three parts, w=xyz satisfying the following condition:

• For each i>=0, xyiz ? L.
• |y| > 0
• |xy| <= n

|w| represents the length of string w and yimeans that i copies of y are concatenated together, y0 = ?.

Applying Pumping Lemma

We will use above theorem to prove that given language is not regular. The steps needed to prove that given languages is not regular are given below:

Step1: Assume L is a regular language in order to obtain a contradiction. Let n be the number of states of corresponding finite automata.

Step2: Now chose a string w in L that has length n or greater

i.e.  |w| >= n. use pumping lemma to write

w = xyz with |xy| <= n and |y| = 0.

Step3: Finally demonstrate that we cannot pumped by considering all ways of dividing w into x, y and z, and for each such division find a value of I such that xyiz ? L. This contradicts our assumption; hence L is not regular.

We prove xyiz ? L by considering the length of xyz i.e. |xyiz| or by using the structure of strings in L.

Example

Let L= { anbn | n>=0 }. By using pumping lemma show that L is not regular language.

Solution:

Step1: Assume L is a regular language in order to obtain contradiction. Let n be the number of states in finite automata accepting L.

Step2: Let w = anbn,  then |w| = 2n > n. Using pumping lemma, we can demonstrate w in three parts of xyz such that w = xyz with |xy| <=n and |y| > 0.

Step3: Now we want to find i, xyiz ? L.

There are three possibilities for y, we will consider all cases one by one and show that given language contains some string not for { anbn | n>=0 }.

Case 1: The string y consists of only a’s i.e. y = ak  (k>=1).

We have w = xyz

                w = anbn

In given language we have equal numbers of a’s and b’s w ? L so it must satisfy this condition. Let us take i=0.

As            xyz = anbn

                xz   = an-kbn

               n-k ? n

So xz ? L. This case is a contradiction.

Case 2: The string y consists of only b’s i.e. y = bm  (m >= 1).

We have w = xyz

                w = anbn

In given language, we have equal number of a’s and b’s w ? L, so it must satisfy this condition. Let us take i=0.

As            xz = anbn-m

                xz   = an-kbn

Where      n ? m

So xz ? L. This case also gives contradiction.

Case 3: The string y consists of both a’s and b’s i.e. y = akbm  (k,m >= 1).

We have w = xyz

                w = anbn

                w = an-kakbm bn-m

In given language we have equal number of a’s and b’s w ? L, so it must satisfy this condition. Let us take i=2.

                xy2z = xyyzi

                        = an-kakbmkbm bn-m

In this case, the string xyyz must have equal number of a’s and b’s but they are out of order with some b’s before a’s. Hence it is not a member of L. which contradicts our assumption.

Thus, in all cases we get a contradiction. Therefore, L is not regular.

Applications of Pumping Lemma

Pumping Lemma is to be applied to show that certain languages are not regular. It should never be used to show a language is regular.

• If L is regular, it satisfies Pumping Lemma.

• If L does not satisfy Pumping Lemma, it is non-regular.

Example:

Prove that L = {aibi | i ≥ 0} is not regular.

Solution −

• At first, we assume that L is regular and n is the number of states.

• Let w = anbn. Thus |w| = 2n ≥ n.

• By pumping lemma, let w = xyz, where |xy| ≤ n.

• Let x = ap, y = aq, and z = arbn, where p + q + r = n, p ≠ 0, q ≠ 0, r ≠ 0. Thus |y| ≠ 0.

• Let k = 2. Then xy2z = apa2qarbn.

• Number of as = (p + 2q + r) = (p + q + r) + q = n + q

• Hence, xy2z = an+q bn. Since q ≠ 0, xy2z is not of the form anbn.

• Thus, xy2z is not in L. Hence L is not regular.

Example 3:

Solution:

L2 = {xx | x ∈ {0, 1}*} is not regular.
We show that the pumping lemma does not hold for L2. Consider any pumping number
p ≥ 1. Choose w = 10^p10^p. Consider any pumping decomposition w = xyz; all we know about xyz is that
|y| > 0 and |xy| ≤ p. There are two possibilities:

(a) x = 10^aand y = 0^b and z = 0^p-a-b10^p, for b ≥ 1.
(a) x = " and y = 10b and z = 0^p-b10^p1.
Choose i = 2. We need to show that xy²z is not in L2.
In case (a), xy2z = 10^p+b10^p, which is not in L2 because b ≥ 1.
In case (b), xy2z = 10^b10^p10^p, which is not in L2 because it contains three 1’s.

Example 4:

We prove that L3 = {1ⁿ² | n ≥ 0} is not regular.
Solution:
We show that the pumping lemma does not hold for L3. Consider any pumping number p ≥ 1.
Choose w = 1^p2.
Consider any pumping decomposition w = xyz such that |y| > 0 and |xy| ≤ p. It follows
that x = 1^a and y = 1^b and z = 1^p2
−a−b, for b ≥ 1 and a + b ≤ p. Choose i = 2. We need to show that
xy²z = 1^n2+b is not in L3; that is, we need to show that p2 + b is not a square. Since b ≥ 1, we have
p2 + b > p2. Since a + b ≤ p, we have p2 + b ≤ p2 + p < (p + 1)2 

Example 5:

Prove that Language L = {0n: n is a perfect square} is irregular.
Solution: 

L is infinite. Suppose L is also regular. Then according to pumping lemma there exists an integer n such that for every string w in where |w| >= n, we can break w into three strings w = xyz such that:
|y| > 0 , |xy| <= n and for all k>=0 , the string xy^kz is also in L.
Choose w to be w = 0s where s = n² that is it is a perfect square.
Let w= 00000000000000000………00000 = xyz . (The length of w = s = n² in this case.)
Let |xy| <= n and |y| = k. That is w = 0000 0k 000… X y z So, |xyz| = |xz| + |y| = (n²- k ) + (k) From pumping lemma, I can pump y any number of times and the new string should also belong to the language. Suppose I pump y twice then, the new string should belong to the language that is it should have length that is a perfect square but, |xy2z| = |xz| + 2|y| = (n²- k ) + 2k = n² + k where n² + k < 1 =" (n+1)(n+1)"> n² (As k > 0)
=> n² <>2 + k < (n+1)2 => n² + k is not a perfect square
=> xy²z is not in L
=> This is a contradiction to the pumping lemma
So, our initial assumption must have been wrong that is L is not regular.