# Decide whether DFA have useless states

A useless state in a DFA is one that is never entered on any input string. Consider the problem of determining whether a DFA has any useless states. Formulate this problem as a language and show that it is decidable.

I know how to prove it with Turing Machines, but not DFAs. So here is my proof for TM:

Let $U_{\mathrm{TM}} = \{\left \langle M \right \rangle|M \text{ is a TM that has a useless state}\}$. We show that $U_{\mathrm{TM}}$ is undecidable by a reduction from $\mathrm{HALT_{TM}}$ to $U_{\mathrm{TM}}$:

If $\left \langle A,w \right \rangle \in \mathrm{HALT_{TM}}$, then $A$ halts on input $w$ and $M_A$ visits all its states on every input; thus, $\left \langle M_A \right \rangle \notin U_{\mathrm{TM}}$. iIf $\left \langle A,w \right \rangle \notin \mathrm{HALT_{TM}}$, then $A$ loops on input $w$ and so does $M_A$; therefore, $M_A$ will never visit state $q_u$ and $\left \langle M_A \right \rangle \notin U_{\mathrm{TM}}$. Since $\mathrm{HALT_{TM}}$ is undecidable, $U_{\mathrm{TM}}$ is undecidable.

But for DFA I have to show that the language is DECIDABLE. Do you have any ideas how I can go with that?

• Hint: given any state in a DFA, how do you explicitly construct an input on which that state is reached? Does that ever not work, and if so when? – Raphael Nov 12 '14 at 15:02
• "A useless state in a DFA is one that is never entered on any input string." -- accepted inputs or all of them? – Raphael Sep 29 '17 at 4:48

Given a DFA $A$, run a BFS from the initial state ($q_0$), and mark every node that is being visited.
• That does not find all useless states: some may be reachable from $q_0$, but as long as you can't reach a final state from there they're useless. – Raphael Sep 28 '17 at 16:49