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?