# Is there a bound on possible Dead state in a minimized DFA

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?

• Yes, and you can prove that formally. Apr 5, 2021 at 9:18
• 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. Apr 5, 2021 at 17:37

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.