Number of final states in a minimal DFA

Is the number of final states in a DFA at least the number of final states in its minimal DFA?

Is the answer even yes? Any help would be appreciated.

• I am afraid that you have accepted an answer that is wrong. Otherwise, could you please point out where my answer is not good enough? – Apass.Jack Mar 7 at 18:43

No. An easy counterexample to think about is a line of states that are all final states and they transition to the right on 0 or 1. So like A ->(0,1) B -> (0,1) -> C -> (0,1) C where the final node simply loops on itself for 0 and 1. Using Myhill-Nerode this would simplify down to a single start state that loops on itself. So the number of final states isn't necessarily a construction on the number of states after minimizing.

• I'm not sure whether that counterexample is valid, since there are fewer final states in the minimal DFA than the preminimization DFA. What I was asking is that, for any DFA, the number of final states in it is less than or equal to the number of final states in its minimal DFA. – Johnny Wang Mar 7 at 17:34
• @JohnnyWang Please don't accept an answer until you're sure that it actually answers your question. In particular, Justin can't delete this answer because it's the accepted one. – David Richerby Mar 7 at 19:09

Yes, the number of final states in a DFA is at least the number of final states in its minimal DFA. Your proof is correct at some level of formality.

Intuitively, as you have noticed, any DFA for $$L$$ can be reduced to the minimal DFA for $$L$$ by merging states, which must merge any final states to a final state.

Here is how to make your proof mathematically more formal. Let $$L$$ be a language over $$\Sigma$$ and $$D=(Q,\Sigma,\delta,s,F)$$ be a DFA that accepts $$L$$. Let $$M$$ be the set of Myhill-Nerode equivalence classes with respect to $$L$$.

Define a map $$m:Q\to M$$ such that $$m(q)=[w]$$, where $$w$$ is any input that will drive $$D$$ to state $$q$$ and $$[w]$$ is the Myhill-Nerode equivalence class that contains $$w$$. We can verify that $$m$$ is well-defined, i.e., $$[w_1]=[w_2]$$ if both $$w_1$$ and $$w_2$$ drive $$D$$ to $$q$$.

We can verify or recall the following claims, thus completing this proof.

• $$m$$ maps a final state in $$D$$ to a Myhill-Nerode equivalence class that contains a word in $$L$$.
• all final states in the minimal DFA of $$L$$ are in one-to-one correspondence to all Myhill-Nerode equivalence classes that contain a word in $$L$$.

Here is a simple related exercise.

Exercise. The number of non-final states in a DFA is at least the number of non-final states in its minimal DFA.