1
$\begingroup$

I am trying to use Myhill-Nerode theorem to minimize the DFA appearing below.

The algorithm repeatedly runs the following step:

If there is an unmarked pair $(Q_i, Q_j)$, mark it if the pair $\{δ (Q_i, A), δ (Q_j, A)\}$ is marked for some input letter.

Initially only $\{0,3\},\{1,3\},\{2,3\}$ are marked. However, $\{0,1\}$ or $\{0,2\}$ won't be marked since the don't have common edges, $\{1,3\},\{1,2\}$ or $\{2,3\}$ only goes to state 3 with edge 3, but there is no such pair $\{3,3\}$. Then it seems no minimization can be done.

The minimized DFA, however, should merge states 1 and 2.

dfa

$\endgroup$
  • $\begingroup$ Your question is well written. However, haven't you answered your own question by "But state 1 and 2 can be merged"? Once state 1 and 2 are merged, you get the minimal DFA, assuming the alphabet is $\{1,2,3\}$. $\endgroup$ – Apass.Jack Oct 7 '18 at 18:42
  • $\begingroup$ @Apass.Jack, yes,the minimum DFA should have states: {0}, {1,2}, {3}. But I followed Myphill-Nerode Theorem, I don't know how exactly it is done. $\endgroup$ – worldterminator Oct 8 '18 at 3:47
2
$\begingroup$

The difficulty with the problem is, as Dean Gurvitz hinted and as you have experienced, not all transitions are specified explicitly. For example, given input 3 at state 0, what is the transition? According to the definition of DFA, every transition for any input symbol at any state must be specified.

You will ask then, why do I see such a graph for a DFA? What you see is a DFA specified as an incomplete DFA.

some authors use deterministic finite automaton for a slightly different notion: an automaton that defines at most one transition for each state and each input symbol; the transition function is allowed to be partial. When no transition is defined, such an automaton halts.

To apply your procedure to minimize a DFA, you have to convert an incomplete DFA to a (complete) DFA. Add another state $R$, the rejected state. Whenever a transition from some state given some symbol is not specified, add a transition from that state given that symbol that goes to $R$. In particular, all transitions that start from $R$ go to $R$. Now that a (complete) DFA if formed, you can compute merrily with your procedure, treating $R$ just as any other non-final state. Once you are done with your procedure, you will have a (complete) DFA with minimal states. If preferred or necessary, you can convert the minimal (complete) DFA to an incomplete DFA by removing the (new) rejected state, i.e., the state that comes from $R$, and all transitions from or to that state.

$\endgroup$

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.