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?


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).

  • $\begingroup$ 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$? $\endgroup$ – maddie Mar 12 '18 at 17:43
  • $\begingroup$ Right, state equivalence is an equivalence relation. $\endgroup$ – Yuval Filmus Mar 12 '18 at 17:44

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.