Question: (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

(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 w E L, such that [w] > p. iii. Let w = xyz, so that |xy|
0. iv. Then xyz 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.)
Step by Step Solution
There are 3 Steps involved in it
Get step-by-step solutions from verified subject matter experts
