0
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ 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? $\endgroup$ – Raphael Nov 12 '14 at 15:02
  • $\begingroup$ "A useless state in a DFA is one that is never entered on any input string." -- accepted inputs or all of them? $\endgroup$ – Raphael Sep 29 '17 at 4:48
1
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – Raphael Sep 28 '17 at 16:49
  • $\begingroup$ @Raphael Huh? The question defines "useless" as meaning "never entered on any input string" not "never entered on any accepted input string." You're welcome to argue that states from which no accepting state is reachable can also be optimized away, but that's not what this question is asking about. $\endgroup$ – David Richerby Sep 28 '17 at 22:18
  • $\begingroup$ @DavidRicherby True, my bad. $\endgroup$ – Raphael Sep 29 '17 at 4:47

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.