# Useless states in a PDA

I am trying to solve a problem in Sipser's Introduction to the Theory of Computation book, which reads:

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

I feel that I have a solution, but at the same time the solution makes no reference to the fact that the machine in question is a PDA, which makes me suspicious. Here is my proposed solution:

Formulate the problem as the language $$L = \{\langle M, q, w \rangle \mid M \text{ is a PDA }, q \text{ is a state of M}, w \text{ is any word in } \Sigma(M)^*\}.$$ Then to decide this language, simply run $$w$$ in $$M$$, and see if we ever encounter $$q$$. Since PDAs are non-deterministic by definition, there may be branching choices, and so we just go through all possible branches. We accept if we encounter $$q$$ at some point, and reject if we don't. Since the PDA can't loop, then this process won't loop either, and so $$L$$ is decidable.

This seems to work to me, but as mentioned, it makes no real use of PDAs. It seems like this argument would also work if $$M$$ was more generally a Turing-decider. So basically, my question is, is this argument truly valid, or am I missing something? My only thought is that perhaps this language is not a true formulation of the problem. If so, how does one understand whether the language they have written is a correct formulation or not?

Thanks for reading, and for any insight.

Your formulation of the language is wrong. Your language is a collection of pushdown automata. A PDA $$M$$ is in your language if it has no useless states. This means that for every state $$q$$, there is an input $$w$$ and a run of the PDA on $$w$$ which causes $$M$$ to enter $$q$$.

Moreover, PDAs can definitely loop, since they have $$\epsilon$$ transitions, so your solution doesn't quite work even for your language. It definitely doesn't work for Turing machines; indeed, if $$M$$ is a Turing machine, then your language becomes undecidable.

• Thanks for the response. I see now that the language $L$ I defined is not even what is modeled by my description below. Instead, should my language be $\{<M> | M \text{ is a PDA with a useless state}\}$? And I want some decider which, given an input of any PDA $M$ (regardless of whether it has a useless state or not), determines whether it has a useless state via some process which will always terminate?
– t42d
Mar 6 at 19:09
• Right, you got it. Mar 6 at 19:17
• Thanks! One last question. How did you modify the question? I see that the image I inserted has now been changed to some block format, but I don't know how that was achieved. Is that block format a standard convention on this site?
– t42d
Mar 6 at 20:01
• You can press the Edit button to see the source code of the post. In general, text is preferable since search engines index it. Mar 6 at 21:24
• Got it. Thanks for your help!
– t42d
Mar 6 at 21:48