1. Showthat there is a nonnegative integer n such that the set of n-equivalence classes of states of M is the same as the set of (n + 1)-equivalence classes of states of M. Then show for this integer n, the set of n-equivalence classes of states of M equals the set of ∗-equivalence classes of states of M.
The quotient automaton M of the deterministic finite-state automaton M = (S, I, f, s0, F) is the finite-state automaton (S, I, ( , [s0]R∗ , F), where the set of states S is the set of ∗-equivalence classes of S, the transition function f is defined by f ([s]R∗ , a) = [f (s,a)]R∗ for all states [s]R∗ of M and input symbols a ∈ I , and F is the set consisting of R∗- equivalence classes of final states of M.
2. a) Show that if M is a finite-state automaton, then the quotient automaton M recognizes the same language as M.
b) Show that if M is a finite-state automaton with the property that for every state s of M there is a string x ∈ I ∗ such that f (s0, x) = s, then the quotient automaton has the minimum number of states of any finite-state automaton equivalent to M.