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

The Explanation have got it all Go through the explanations.

Explanation:

Define the decision problem with the language

USELESS TM = {hM, qi | q is a useless state in TM M }.

We show that USELESS TM is undecidable by reducing ETM to USELESS TM, where

ETM = { hMi | M is a TM and L(M) = ∅ }. We know ETM is undecidable by Theorem 5.2.

Assume that USELESS TM is decidable and that TM R decides it. Note that for any

Turing machine M with accept state qaccept, qaccept is useless if L(M) = ∅.

Thus, because TM R solves USELESS TM, we can use R to check if qaccept is a useless

state to decide ETM. Specifically, below is a TM S that decides ETM by using the

decider R for USELESS TM as a subroutine:

S = “On input hMi, where M is a TM:

1. Run TM R on input hM, qaccepti, where qaccept is

the acceptable state of M.

2. If R accepts, accept. If R rejects, reject.”

However, since we know that ETM is undecidable, there cannot exist a TM that decides

USELESS TM.

answer; i believe the correct answer is (expression); good luck

(because i need 20 chars)