3. Consider the language L = {uw l u and w are strings over {0,1} and have the s

Question

3. Consider the language L = {uw l u and w are strings over {0,1} and have the same number of 1s). Find the error in the following attempted proof that L is not regular: "Proof" that L is not regular using the Pumping Lemma: Assume (towards a contradiction) that L is regular. Then the Pumping Lemma applies to L. Let p be the pumping length of L. Choose s to be the string 1POP1POP, which is in L because we can choose u = 1p0p and w 1rop which each have p 1s Since s is in L and has length greater than or equal to p, the Pumping Lemma guarantees that s can be divided into parts z, y, z where s ryz, lyl > 0, Jry p, and for each i > 0, zy'z E L Since the first p letters of s are all 1 and ry p, we know that z and y are made up of all 1s. If we let i = 2, we get a string zy'z that is not in L because repeating y twice adds is to but not to w, and strings in L are required to have the same number of 1s in u as in w This is a contradiction. Therefore, the assumption is false, and L is not regular.

Explanation / Answer

As given by L = {uw | u and w are strings over inputs {0,1} and have the same number of 1s}. So in order to prove that L is not Regular we first need to assume a contradiction that say L is Regular and by using Pumping-Lemma we will furthur see that if it doesnt satisfies the Pumping Lemma criteria then L is not a Regular Language.

Let's consider the Pumping Length (P) = 5. So uw can be written as (01)P(01)P, which can be broken down as 0P1P0P1P. Our target is to prove that this 0P1P0P1P expression is not Regular.

CASE 1:- Let uw = 00000111110000011111. Lets break this into 3 parts x,y and z, where x = 0, y = 0, z = 000111110000011111. So |y| = 1, which is greater than 0. Also |xy| = 1 <= 5, which is still true. Now xyiz should belong to L for i=2 (say), we get 000000111110000011111. Clearly we see that 000000111110000011111 does not match 0P1P0P1P, as we have more number of zero as compared to 1. Hence this violates the last criteria of pumping lemma and so L is Not Regular.

CASE 2:- Let uw = 00000111110000011111. Lets break this into 3 parts x,y and z, where x = 00000, y = 1, z = 11110000011111. So |y| = 1, which is greater than 0. Also |xy| = 5 <= 5, which is still true. Now xyiz should belong to L for i=2 (say), we get 000001111110000011111. Clearly we see that 000001111110000011111 does not match 0P1P0P1P, as we have more number of 1 as compared to 0. Hence this violates the last criteria of pumping lemma and so L is Not Regular.

Please let me know in case of any clarifications required. Thanks!

Related Questions

Navigate

• Browse (All)
• Browse 3
• Subjects

---

---

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