2. (7 points) Common Pumping Lemma Misunderstandings (a) (2 points) You are a CS4510 TA, and you are grading the following question: "Is the language L = {w w is a binary string with at least as many l's as 0's) regular? Prove your answer." Bob, a student in the class, has submitted the following answer: I will prove that L is not regular, using the pumping lemma. i. Let pezt. ii. Let w = 01', so that we L and W > p. iii. Let w = xyz, with x = e, y = 0, and 2 = 1P, so that my

0. iv. Then cyP+1, is not in L. Identify the single incorrect line in Bob's proof and explain what he did wrong. (NOTE: do not list small mistakes, typos, etc.; explain the major logical error which invalidates Bob's proof.) (b) (2 points) Now you are grading the following problem: "Let L be any finite, nonempty language of binary strings. Is L regular?" Katharine has submitted the following answer: I will prove that L is not regular, using the pumping lemma. i. Since L is finite, it has a longest string. Let p be the length of the longest string in L. ii. Let wel, such that w p . iii. Let w = ryz, so that my

0. iv. Then zy z is not in L, since it has length longer than p, but all the strings in L have length at most p. Identify the single incorrect line in Katharine's proof, and explain what she did wrong. (NOTE: Do not just say, "L is actually regular"; explain the major logical error which invalidates Katharine's proof.) 2. (7 points) Common Pumping Lemma Misunderstandings (a) (2 points) You are a CS4510 TA, and you are grading the following question: "Is the language L = {w w is a binary string with at least as many l's as 0's) regular? Prove your answer." Bob, a student in the class, has submitted the following answer: I will prove that L is not regular, using the pumping lemma. i. Let pezt. ii. Let w = 01', so that we L and W > p. iii. Let w = xyz, with x = e, y = 0, and 2 = 1P, so that my

0. iv. Then cyP+1, is not in L. Identify the single incorrect line in Bob's proof and explain what he did wrong. (NOTE: do not list small mistakes, typos, etc.; explain the major logical error which invalidates Bob's proof.) (b) (2 points) Now you are grading the following problem: "Let L be any finite, nonempty language of binary strings. Is L regular?" Katharine has submitted the following answer: I will prove that L is not regular, using the pumping lemma. i. Since L is finite, it has a longest string. Let p be the length of the longest string in L. ii. Let wel, such that w p . iii. Let w = ryz, so that my

0. iv. Then zy z is not in L, since it has length longer than p, but all the strings in L have length at most p. Identify the single incorrect line in Katharine's proof, and explain what she did wrong. (NOTE: Do not just say, "L is actually regular"; explain the major logical error which invalidates Katharine's proof.)