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 (b) The language L uo and w are strings over (0, 1) and have the same length) "Proof" that L2 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 L2. Choose s to be the stringP which is in L2 because we can choose 1P and wP which each have length p. Since s is in L2 and has length greater than or equal to p, if p were to be a pumping length for L2, s ought to be pump'able. That is, there should be a way of dividing s into parts x, y, z where s = xyz, > 0, |xy| 0, xy's E L. When x = and y have satisfied that s- ryz, ly> 0 (because p is positive) and |ryl S p. If we let i 2, we get the string ry'z 12PO+ that is not in L2 because its middle symbol is a 1, not a 0. 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 L2. Since p was arbitrary, we have demonstrated that L2 has no pumping length. By the Pumping Lemma, this implies that L2 is nonregular pti, we and 2