Consider the algorithm MINIMIZE, which takes a DFA M as input and outputs DFA M'. MINIMIZE = On input hMi, whereM = (Q,, , q

Consider the algorithm MINIMIZE, which takes a DFA M as input and outputs DFA M'. MINIMIZE = “On input hMi, whereM = (Q,Σ, δ, q₀,A) is a DFA:

1. Remove all states of M that are unreachable from the start state.

2. Construct the following undirected graph G whose nodes are the states of M.

3. Place an edge in G connecting every accept state with every nonaccept state. Add additional edges as follows.

4. Repeat until no new edges are added to G:

5. For every pair of distinct states q and r of M and every a ∈ Σ:

6. Add the edge (q, r) to G if (δ(q, a), (r, a)) is an edge of G.

7. For each state q, let [q] be the collection of states [q] = {r ∈ Q| no edge joins q and r in G}.

8. Form a new DFA M0 = (Q₀, Σ, δ', q₀',A') where Q' = {[q]| q ∈ Q} (if [q] = [r], only one of them is in Q'), δ'([q], a) = [δ(q, a)] for every q ∈ Q and a ∈ Σ, q₀' = [q₀], and A' = {[q]| q ∈ A}.

9. Output 〈M₀〉.”

a. Show that M and M' are equivalent.

b. Show that M' is minimal—that is, no DFA with fewer states recognizes the same language. You may use the result of Problem 1.52 without proof. c. Show that MINIMIZE operates in polynomial time.