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