1. (22 points) Do the following for each of the following attempted "proofs" that a set is nonregular: i Find the (first and/or most significant) logical error in the "proof" and describe why it's ii Either prove that the set is actually regular (by finding a regular expression that describes it wrong. 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 Lu u and w are strings over (0,1) and have the same length) "Proof that Li 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 L1 Choose s to be the string 1POP, which is in L1 because we can choose 1P and w = 0p which each have length p. Since s is in L1 and has length greater than or equal to p, if p were to be a pumping length for L1, s ought to be pump'able. That is, there should be a way of dividing s into parts x, y, z where s = xyz, ly| > 0, |xy| p, and for each i > 0, xy"z L. Suppose x, y, z are such that s-, >0 and y p. Since the first p letters of s are al 1 and y p, we know that x and y are made up of all 1s. If we let i = 2, we get a string xy's that is not in L1 because repeating y twice adds ls 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 L. Since p was arbitrary, we have demonstrated that L1 has no pumping length. By the Pumping Lemma, this implies that L is nonregular (b) The language L2 = {u0w I u and u, 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 string 1POP+1, which is in L2 because we can choose1P and w = 0p 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, ly| > 0, ryp, and for each i 2 0, ry'z L. When E and y 1P and+, we have satisfied that s ryz, y0 (because p is positive) and |ry| S p. If we let i -2, we get the string ry'z12'op+1 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
