For the following proofs:

- find the logic errors and explain why it is wrong

- prove the set is regular OR fix the logic of the proof

- construct a PDA that describes the language

(a) The language L1-fuw | u and w are strings over 10, 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 IpOP, which is in Li because we can choose u = 1p and w0P 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 r, y, z where s - ryz, ly > 0, ryp, and for each i 2 0, ry'z e L. Suppose r, y, z are such that syz, 0 and ryl S p. Since the first p letters of s are a and ryl S 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 Li because repeating y twice adds 1s to u but not to w, and strings in L1 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 Li has no pumping length. By the Pumping Lemma, this implies that L1 is nonregular (b) The language L2 {u0w I 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 1P and w -0" 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-ryz, y>0 layl-p, and for each i > 0, xy'z E L. When x and y = 1p and z = 0p+1, we have satisfied that s yz, y > 0 (because p is positive) and y p. If we let i = 2. we get the string 2u'z = 12p0p+1 that is not in L2 because its middle svmbol 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