3. Consider the language L (uw | u and w are strings over 0,1 and have the same

Question

3. Consider the language L (uw | 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 1pOP1P0, which is in L because we can choose u = 1p0p and w = 1POP 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 x, y, z where s xyz, lul > 0, Ixy| p, and for each i-0, zyi2E L. Since the first p letters of s are all 1 and |xy p, we know that a and y are made up of all 1s. If we let i-2, we get a string ry'z that is not in L because repeating y twice adds 1s to u 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

Given: L {uw | u and w are strings over {0,1} and have the same number of 1s}

prove: L is not Regular

In order to prove that L is not Regular initially, assume that L is regular by using Pumping-Lemma.

Let's consider, Pumping Length (P) = 5.

Therefore, uw can also be written as (01)P(01)P, which can be written as 0P1P0P1P. Our objective is to prove that 0P1P0P1P expression is not Regular.

Consider: uw = 00000111110000011111. Lets break this into 3 parts x,y and z, where x = 0, y = 0, z = 000111110000011111. So |y| = 1, that 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 there is an additional number of zero as compared to 1. Hence this violates the last criteria of pumping lemma and so L is Not Regular.

Hence, proved L is not Regular.

Related Questions

Navigate

• Browse (All)
• Browse 3
• Subjects

---

---

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