# 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\}$. – Apass.Jack 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. – worldterminator Oct 8 '18 at 3:47

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.