Counterexample for minimal DFA proof

Question

I'm struggling with a following task: Let $A = (Q, Σ, δ, q_{0}, F)$ be a DFA, in which every state is attainable (attainable state meaning that there exists a word that after reading that word, the automata will end up in said state). Is it possible to ALWAYS modify F in such way that the automata will be minimal?

So basically we have to think if it is always possible to modify F in an automata such that the automata will be minimal after that modification.

I know, that if we have a DFA with N states, then we have $2^N$ options to choose F from. We have to find a counterexample DFA in which for every F picked there will be an option to further minimize the DFA.

I can't find a counterexample for that, could you help me with this task or maybe somehow narrow it down to some examples?

THANKS!

Answer 1

Possible Method: Let's assume there are no un-reachable nodes. Then DFA minimization works on the assumption that there are equivalent, non-distinguishable nodes. Lets say there are two equivalent nodes, then one can always set one of the equivalent nodes to be in F and the other to not be in F, and thus distinguish them.

But what if there are more than 2 equivalent nodes? In such cases, even after changing F, some 2 nodes may remain non-distinguishable. Concretely consider the following example:

In this case, the DFA accepts all words of size 2 or more. Can we find some subset of accepting states for which this is the minimal DFA? $C_0,C_1$ must be distinguished, so one must be accepting and the other not. Similarly, $D_0,D_1$ must be distinguished, so one must be accepting and the other not. But then, the accepting states, say $C_0,D_1$ can be merged and so can $C_1,D_0$ as they are non-distinguishable. So we cannot find any subsets of accepting states for which this is minimal.

Answer 2

Yes, there is a counterexample. Consider the automaton $(Q, A, i, \cdot)$ where $Q = \{1, 2, 3, 4, 0\}$, $A = \{a, b, c\}$, $i = 1$ and the transitions given by $1 \cdot a = 2$, $1 \cdot b = 3$, $1 \cdot c = 4$, and, for each letter $x$, $2 \cdot x = 2$, $3 \cdot x = 3$, $4 \cdot x = 4$, $0 \cdot x = 0$ and all other missing transitions are of the form $q \cdot x = 0$.

I let you verify that two states from the set $\{2, 3, 4\}$ are necessarily equivalent.