This question reveals important subtleties of the Pumping Lemma. Let B = {0^k x0

Question

This question reveals important subtleties of the Pumping Lemma. Let B = {0^k x0^k k greaterthanorequalto 1 and x sigma *}. (a) Consider the following argument, which claims to prove that B is not regular. Assume B_2 is regular, and let p be the pumping length. Consider string s = 0^P10^P B_2, and decompose it as s = xyz with x =, y = 0^P, z = 10^p. Then, pumping s down by setting i = 0 yields string s' = xy^iz = xy^0 z = 10^p B_2. Hence, by the Pumping Lemma, we have a contradiction. We conclude that B_2 is not regular. The question is: What is wrong with this proof? (b) Prove that, in fact, B is regular.

Explanation / Answer

Ans (a) In pumping lemma we assume that B is regular and let n be the number of states.

Then we consider a string w such that

|w| > c , where c is a constant

And we break w such in x, y and z

w = xyz such that

|y| > 0

|xy|>= c

and for all k>=0 it satisfy |xykz| should be in B

Here in above solution you have assumed i=0 for which

|y|=0 and which is wrong in this proof.

So if you consider y=2 then this also S'=xy2z , S not belongs to B2and by pumping lemma we can say that B2 is not regular

Ans (b) We can use pumping lemma for proving any language to be not regular it should not be used for proving a language to be regular

If 'l' is regular it satisfy pumping lemma

anf if l is not regular it does not satisfy pumping lemma

so we can't prove by pumping lemma that B is regular

Related Questions

Navigate

• Browse (All)
• Browse T
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.