i Find the (first and/or most significant) logical error in the "proof" and describe why it's wrong. ii Either prove that the set is actually regular (by finding a regular expression that describes it or a DFA/NFA that recognizes it, and justifying why) or fix the proof so that it is logically sound iii Draw the state diagram of a PDA that recognizes the language. Briefly describe the role of each state in the PDA (a) The language L1- [uw|u and w are strings over {0, 1} and have the same length}. "Proof' that L1 is not regular using the Pumping Lemma: Let p be an arbitrary positive integer. We will show that p is not a pumping length for Li Choose s to be the string 1POP, which is in L1 because we can choose u 1P and w 0P which each have length p. Since s is in Li and has length greater than or equal to p, if p were to be a pumping length for Li, s ought to be pump'able. That is, there should be a way of dividing s into parts x, y, where s-xyz, |y| > 0, |xy| p, and for each i 0, xy'z E L. Suppose x, y, z are such that s = xyz, y0 and xyp. Since the first p letters of s are all 1 and |ry| S p, we know that x and y are made up of all 1s. If we let i 2, we get a string xyi that is not in L1 because repeating y twice adds 1s to u but not to w, and strings in LI are required to have u and w be the same length. Thus, s is not pumpable (even though it should have been if p were to be a pumping length) and so p is not a pumping length for L1. Since p was arbitrary, we have demonstrated that L has no pumping length. By the Pumping Lemma, this implies that Li is nonregular