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.
Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It only takes a minute to sign up.Sign up to join this community
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.
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.
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.