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 ustifying why) or fix the proof so that it is logically sound ii Draw the state diagram of a PDA that recognizes the language. Briefly describe the role of each state in the PDA (a) The language Luw u and w are strings over [0, 1) and have the same length) Proof" that L 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 L 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 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, y > 0 |xy| p, and for each i > 0, xy's E L. Suppose x, y, z are such that s = xyz, >0 and y S p. Since the first p letters of s are a 1 and yp, we know that x and y are made up of a s. If we let i- 2, we get a string xyz 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 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 L1 has no pumping length. By the Pumping Lemma, this implies that L1 is nonregular. (b) The language L,-(u0 u 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 string 1POP+1, which is in L2 because we can choose u1P 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, y > 0 |xy| p, and for each i > 0, xy's E L. When x = and y = 1P and z-OP+1, we have satisfied that s = xyz, |y| > 0 (because p is positive) and |xy|-P. If we let i-2, we get the string ry'z 12Pthat 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
