2
$\begingroup$

I want to know if a DFA is minimized, is there an upper bound on how many dead states are possible when it is in its minimal form, in terms of number of states, etc?

Intuitively, I am thinking that it is at most one, because if other state is there from where accept state is not reachable, the minimization would merge the states, because it is serving no more purpose than the other dead state. Is my intuition true?

$\endgroup$
2
  • 2
    $\begingroup$ Yes, and you can prove that formally. $\endgroup$ – Steven Apr 5 at 9:18
  • 1
    $\begingroup$ One possible intuition-based (rather than formalism-based) answer: If there's two dead states A and B, you can redirect all the edges leading to A to point at B instead to get a smaller automaton with the same language. $\endgroup$ – Daniel Wagner Apr 5 at 17:37
2
$\begingroup$

If you allow the DFA to be trimmed, then you can delete ALL dead states. If you want the DFA to be complete, then the minimized DFA will indeed have at most one dead state.

The reason is that minimizing leads you to merge nondistinguishable states, that is equivalent states in the Myhill-Nerode equivalence relation (here the definition is given for words and languages, but it can be extended to automata).

Two states $q_1, q_2$ are distinguishable if there exists a word $u$ such that $\delta^*(q_1, u)$ is final and $\delta^*(q_2, u)$ is not (or the converse). If $q_1, q_2$ are two dead states, then $\delta^*(q_1, u)$ can never be final (and same for $q_2$), so $q_1, q_2$ will never be distinguishable.

$\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.