Steps to solve Pumping Lemma problems:

1. If the language is finite, it is regular , otherwise it might be non-regular.

2. Consider the given language to be regular

3. State pumping lemma

4. Choose a string w from language, choose smartly .

5. Partition it according to constraints of pumping lemma in a generic way

6. Choose a pumping factor k such that the new ‘pumped’ string is not part of the language

given.

7. State the contradiction and end the proof.

How to remember what pumping Lemma says:

Pumping Lemma alternates between “for all” and “there is at least one” or “for every” or

“there exists”. Notice:

For every regular language L

There exists a constant n

For every string w in L such that |w| >= n,

There exists a way to break up w into three strings w = xyz such that |y| > 0 , |xy| <= n and For every k>=0 , the string xykz is also in L.

courtesey: http://suraj.lums.edu.pk/~cs311w05/pumping_lemma_writeup.pdf

1. Show that L2 = {0

We show that the pumping lemma does not hold for L1. Consider any pumping number p; p≥ 1. Choose w = 0

Consider any pumping decomposition w = xyz;

|y| > 0 and |xy| ≤ p. It follows that x = 0

b ≥ 1.

So p+b > p

Hence 0

2. 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

|y| > 0 and |xy| ≤ p. There are two possibilities:

(a) x = 10

(a) x = " and y = 10b and z = 0

Choose i = 2. We need to show that xy

In case (a), xy2z = 10

In case (b), xy2z = 10

3. We prove that L3 = {1

We show that the pumping lemma does not hold for L3. Consider any pumping number p ≥ 1.

Choose w = 1

Consider any pumping decomposition w = xyz such that |y| > 0 and |xy| ≤ p. It follows

that x = 1

−a−b, for b ≥ 1 and a + b ≤ p. Choose i = 2. We need to show that

xy

p2 + b > p2. Since a + b ≤ p, we have p2 + b ≤ p2 + p < (p + 1)2 4.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

Choose w to be w = 0s where s = n

Let w= 00000000000000000………00000 = xyz . (The length of w = s = n

Let |xy| <= n and |y| = k. That is w = 0000 0k 000… X y z So, |xyz| = |xz| + |y| = (n

=> n

=> xy

=> This is a contradiction to the pumping lemma

So, our initial assumption must have been wrong that is L is not regular.

1. If the language is finite, it is regular , otherwise it might be non-regular.

2. Consider the given language to be regular

3. State pumping lemma

4. Choose a string w from language, choose smartly .

5. Partition it according to constraints of pumping lemma in a generic way

6. Choose a pumping factor k such that the new ‘pumped’ string is not part of the language

given.

7. State the contradiction and end the proof.

How to remember what pumping Lemma says:

Pumping Lemma alternates between “for all” and “there is at least one” or “for every” or

“there exists”. Notice:

For every regular language L

There exists a constant n

For every string w in L such that |w| >= n,

There exists a way to break up w into three strings w = xyz such that |y| > 0 , |xy| <= n and For every k>=0 , the string xykz is also in L.

courtesey: http://suraj.lums.edu.pk/~cs311w05/pumping_lemma_writeup.pdf

1. Show that L2 = {0

^{m}1^{m}| x ∈ {0, 1}*} is not regular.We show that the pumping lemma does not hold for L1. Consider any pumping number p; p≥ 1. Choose w = 0

^{p}1^{p}.Consider any pumping decomposition w = xyz;

|y| > 0 and |xy| ≤ p. It follows that x = 0

^{a}and y = 0^{b}and z = 0^{p-a-b}1^{p}, for b ≥ 1. Choose i = 2. We need to show that xy^{2}z = 0^{p+b}1^{p}is not in L1.b ≥ 1.

So p+b > p

Hence 0

^{p+b}1^{p }is not in L.2. 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

^{p}10^{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

^{a}and y = 0^{b}and z = 0^{p-a-b}10^{p}, for b ≥ 1.(a) x = " and y = 10b and z = 0

^{p-b}10^{p}1.Choose i = 2. We need to show that xy

^{2}z is not in L2.In case (a), xy2z = 10

^{p+b}10^{p}, which is not in L2 because b ≥ 1.In case (b), xy2z = 10

^{b}10^{p}10^{p}, which is not in L2 because it contains three 1’s.3. We prove that L3 = {1

^{n2}| n ≥ 0} is not regular.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

^{2}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 havep2 + b > p2. Since a + b ≤ p, we have p2 + b ≤ p2 + p < (p + 1)2 4.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

^{k}z is also in L.Choose w to be w = 0s where s = n

^{2}that is it is a perfect square.Let w= 00000000000000000………00000 = xyz . (The length of w = s = n

^{2}in this case.)Let |xy| <= n and |y| = k. That is w = 0000 0k 000… X y z So, |xyz| = |xz| + |y| = (n

^{2}- 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^{2}- k ) + 2k = n^{2}+ k where n^{2}+ k < 1 =" (n+1)(n+1)"> n^{2}(As k > 0)=> n

^{2}<>2 + k < (n+1)2 => n^{2}+ k is not a perfect square=> xy

^{2}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.