Equivalence relation of DFA (alternative to pumping) Given a DFA M = (Q, sigma, delta, q_0, F), define M(w) = q = delta(...delta(q_0, w_1), w_2)....w_n), i.e. following the transitions based on the symbols of w, puts M in state q. Define w_1 ~ M w_2 to mean that M(w_1) = M(w_2). Also define the extension of w with respect to a language L as: E_L (w) = {z|wz elementof L} We say that w_1 = L w_2 iff E_L (w_1) = E_L (w_2). Observe that = L is an equivalence relation. (a) Find the equivalence classes of the following languages (you can list the different possible E_L (.)): {ab, ac, bb, bc} {a^n b^n|n greaterthanorequalto 0} (b) Show that if w_1 ~ M w_2, then w_1 L (M) w_2. (c) Show that if L is regular, then M has to have at least as many states as the number of equivalence classes of the relation = L (M), and conclude that if the number of equivalence classes of language L is infinite, then L is not regular