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


Draw a table for all pairs of states (P,Q)
Mark all pairs where P is a final state and Q is not a final state. 
If there are any unmarked pairs such that [delta(P,x), delta(Q,x)] is marked, then mark (P,Q) 
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?
It's much better to understand what this marking means. Rather than just follow an algorithm blindly, it's preferable to understand what's going on.

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.

You can show inductively that at the end of Step 3, a pair of states is marked if and only if the two states are inequivalent. Therefore we can merge any pair of unmarked states, obtaining in Step 4 a minimal DFA (again, there is something to prove here).