1
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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? $\endgroup$ – Apass.Jack Mar 7 at 18:43
0
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ 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. $\endgroup$ – Johnny Wang Mar 7 at 17:34
  • 1
    $\begingroup$ Ah yes I misread the question. Please accept the other answer. $\endgroup$ – Justin Clark HEADSHOT9001 Mar 7 at 18:54
  • 1
    $\begingroup$ @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. $\endgroup$ – David Richerby Mar 7 at 19:09
2
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.