# 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? Commented Feb 14, 2019 at 4:07
• @Apass.Jack The question asks for minimization of the DFA, so I didn't think that it would already be minimized. Commented Feb 14, 2019 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"? Commented Feb 14, 2019 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.