How to minimize this DFA using given algorithm?

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.

• 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\}$. Oct 7 '18 at 18:42
• @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. Oct 8 '18 at 3:47

2 Answers

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.

This is a late answer, but I will put a practical twist on the issue.

John L. provides the accepted and formal way of dealing with it. However, from my experience in the industry, instead of halting the machine, it can be treated as self loop.

If it is not mentioned explicitly how to deal with it, go with the accepted answer.

Otherwise, as long as you clearly indicate how unspecified transitions are handled, you can imply things like a reset to initial state, halt state, self loops, some other state...

That will give you different end result, but it will basically completely specify your model.