Problem 4 Suppose M is a DFA, L=L(M), and x and y are strings in *. Argue that if qm (2) Em (y), then x = y. (Advice: again, consider the contrapositive.) Problem 5 Suppose L, SCE*. Suppose that for every pair of distinct strings x and y in S, there is a distinguishing z (in other words, x L y). Suppose L = L(M), for some DFA M. Argue that M has at least |S| states. (Hint: use Problem 4.) Remark: in the previous problem, if S is infinite then there is no DFA, so L is not regular. Problem 4 Suppose M is a DFA, L=L(M), and x and y are strings in *. Argue that if qm (2) Em (y), then x = y. (Advice: again, consider the contrapositive.) Problem 5 Suppose L, SCE*. Suppose that for every pair of distinct strings x and y in S, there is a distinguishing z (in other words, x L y). Suppose L = L(M), for some DFA M. Argue that M has at least |S| states. (Hint: use Problem 4.) Remark: in the previous problem, if S is infinite then there is no DFA, so L is not regular