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 have

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

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

Thanks a gazillion!!!! Keep up the good work!!!

ReplyDeletei think i finally got it.....thanx a lot!

ReplyDeletecan someone help me to understand the first proof?

ReplyDeleteespecially this part

We need to show that xy2z = 0^(p+b)+(1^p) is not in L1. From where did p+b came from? why +b?

Thank you

x = 0^a and y = 0^b and z = 0^(p-a-b)1^p. If you combine x, y and z:

Delete0^a0^b0^b0^(p-a-b)1^p. Notice the double 0^b, since you want the y^2.

Then:

a + b + b + (p-a-b) = 0 -> b + p.

Do you get this?

can anybody help me in solving the que gvn blow

ReplyDeletea language is defined as L={a^n.b^m| n!=m},prove dat L is not regular?

i have a confusion in choosing string W...wat should b d value of w? and also tell the value of 'i', pls tell

thank u!!