# How to minimize this DFA with already merged states?

The original nondeterministic FSA I have is: After converting this to a DFA I get: If I use the Myhill-Nerode theorem on the current DFA, I get all pairs marked, so this is already minimized. But I think this is incorrect.

I want to minimize this DFA. How should I do this using the Myhill-Nerode theorem, since some of the states are merged already?

• "I think this is incorrect." Why? – John L. Feb 14 '19 at 4:07
• @Apass.Jack The question asks for minimization of the DFA, so I didn't think that it would already be minimized. – Ansar Al Feb 14 '19 at 13:20
• "I didn't think that it would already be minimized." Why? What did you mean by "I get all pairs marked, so this is already minimized."? Why did you say "so"? – John L. Feb 14 '19 at 14:18

After inputs $$\epsilon$$, $$a$$, $$ab$$, $$abc$$, $$abca$$ we must be in five different states because appending $$b$$ to one of these leads to an accept only for $$abca$$, appending nothing to any of the others leads to an accept only for $$abc$$, appending $$c$$ leads to an accept only for $$ab$$, appending $$bc$$ to any of the remaining only for $$a$$.
A bit more formally, given a string $$\alpha$$, we note in a 4-tuple whether $$\alpha$$, $$\alpha b$$, $$\alpha c$$, $$\alpha bc$$ are accepted. For $$\alpha = \epsilon, a,ab,abc,abca$$, these 4-tuples are $$(0,0,0,0)$$, $$(0,0,0,1)$$, $$(0,0,1,0)$$, $$(1,0,0,0)$$, $$(1,0,0,1)$$, hence all distintc. This is only possible if these $$\alpha$$ correspond to differnt states.