Decide whether DFA have useless states

Question

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?

Answer 1

In order to show decidability, you need to provide an algorithm that will always halt, and yields a yes / no answer.

The following algorithm will return if there is a useless state in a given DFA (and can return the useless state).

Given a DFA $A$, run a BFS from the initial state ($q_0$), and mark every node that is being visited.

When BFS terminate (and it will, because we're dealing with a deterministic finite automata), every state that wasn't visited during the scan is a useless state.