2
$\begingroup$

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.

$\endgroup$

1 Answer 1

2
$\begingroup$

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.

$\endgroup$
5
  • $\begingroup$ 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? $\endgroup$
    – t42d
    Mar 6 at 19:09
  • $\begingroup$ Right, you got it. $\endgroup$ Mar 6 at 19:17
  • $\begingroup$ 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? $\endgroup$
    – t42d
    Mar 6 at 20:01
  • $\begingroup$ You can press the Edit button to see the source code of the post. In general, text is preferable since search engines index it. $\endgroup$ Mar 6 at 21:24
  • $\begingroup$ Got it. Thanks for your help! $\endgroup$
    – t42d
    Mar 6 at 21:48

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.