# Myhill-Nerode Theorem DFA Minimization

I am learning how to minimize a DFA. One helpful approach is the Myhill-Nerode Theorem, which explains:

1. Draw a table for all pairs of states (P,Q)
2. Mark all pairs where P is a final state and Q is not a final state.
3. If there are any unmarked pairs such that [delta(P,x), delta(Q,x)] is marked, then mark (P,Q)
4. Combine all the unmarked pairs and make them a single state in the minimized DFA.

I'm a little lost on the details of the third step.

In the example here, the unmarked pairs in the resulting table are (a,b), (c,d), (c,e), (d,e). The tutorial combines the latter three into a single state such that there are now two states (a,b) (c,d,e).

What are the rules for combining unmarked pairs? Can you combine two pairs as long as each pair shares a letter with the other? And does the new, merged state take the union of transitions of previous state?

For instance, if state C went to state F on 0 and state D went to state F on 1 and state E never went to state F, then the new, merged state would go to F on 0 or 1, yes?

Let us say that two states $q_1,q_2$ are equivalent if $\delta(q_1,w) \in F$ iff $\delta(q_2,w) \in F$ for any word $w$. The simplest case in which two states are inequivalent is when $q_1 \in F$ but $q_2 \notin F$ (or vice versa). When this happens, we can mark this pair of states as an inequivalent pair of states. This is what happens in Step 2.
In Step 3, we make the following observation. Suppose that $q_1,q_2$ are inequivalent, and that $\delta(r_1,\sigma) = q_1$, $\delta(r_2,\sigma) = q_2$. Then $r_1,r_2$ are also inequivalent (why?). Accordingly, if $r_1,r_2$ is an unmarked pair (not known to be inequivalent) and $\delta(r_1,\sigma),\delta(r_2,\sigma)$ (known to be inequivalent) then we can mark $r_1,r_2$ as inequivalent as well.
• So we could merge $(c,d), (c,e), (d,e)$ because $c$ was equivalent to $d$, which was equivalent to $e$, and thus by the transitive property, $c$ is equivalent to $e$? – maddie Mar 12 '18 at 17:43