Question

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

Answer 1

The Explanation have got it all Go through the explanations.

Step-by-step explanation:

Define the decision problem with the language

USELESS TM = q is a useless state in TM M .

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

ETM = 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.