Useless states in a PDA

Question

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.

Answer 1

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.