Problem 3 Suppose M is a DFA, p and q are states, and a is an input symbol. Argue that if p Em q, then 8(p, a) = S(q, a). (Advice: the contrapositive may be easier.) Problem 4 Suppose M is a DFA, L = L(M), and x and y are strings in *. Argue that if qm(x) =M IM(y), then x =l y. (Advice: again, consider the contrapositive.) Problem 5 Suppose L, S CE*. Suppose that for every pair of distinct strings x and y in S, there is a distinguishing z (in other words, x EL 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