2. Reducibility (16 points) (1) (10 points) For each of the following languages

Question

2. Reducibility (16 points)

(1) (10 points) For each of the following languages either prove it is undecid- able using a reducibility proof or show it is decidable by giving pseudocode for a TM that decides it:

(a) Let FINITETM = {M | M is a TM and M accepts a finite number

of strings}

(b) Let ALLTM = {M | M is a TM and M accepts every string}

(c) Let HALTLBA = {B,w | B is an LBA and B halts on input w}

(d) Let MORECFG = {G1,G2 | G1 and G2 are CFGs where |G1| < |G2|

(i.e., G2 accepts strictly more strings than G1}

(e) Let EMPTYCFG = {G | G is a CFG and G generates }

(2) (2 points) Show that EQCF G = {G1, G2 | G1 and G2 are CFGs where L(G1) = L(G2} is co-Turing-recognizable.

(3) (4 points) A useless state in a Turing machine is one that is never entered on any input string. Consider the problem of testing whether a given state in a Turing machine is a useless state. Formulate this problem as a language and show that it is undecidable.

Hint: Consider the language ETM and whether the accept state is a useless state.

Explanation / Answer

1) a) Let us assume FINITE TM be decidable. Let D be the decider of FINITETM. Now construct S, the decider of ATM using D. S : on input <M,w>

(a) Construct the following TM M0.M0 : on input x

(b) Run D on <M0>. If D accepts, reject <M,w>. If D rejects, accept <M,w>

If M accepts w, the input x is accepted by M0 Or if M rejects w, then input x is accepted by M0 ,  Hence , is recognized by M0 if M accepts w, and is recognised by M0 if M rejects w. Since is infinite and is finite, D accepts its input if M rejects w, and rejects it if M accepts w. Hence FINITETM is undecidable.

(b) By using Rice theorem it is clear that L(M) = is not trivial. If there are two machines two machines M1 and M2 and L(M1) = L(M2). we get the following,

<M1> AllTM L(M1) = = L(M2) <M2> AllTM

Hence by using Rice theorem we prove that ALLTM is Undecidable

(c) HALTLBA = {< B,w > |B is an LBA and B halts on w} is decidable , It because If the LBA stops on input w it must stop in all  (|w|) steps . B has finite number of configurations .

(d)MORECFG = { <G2 | G1> and G2 are CFGs and L(G1)< L(G2) }.

We will reduce ALLCFG to MORECFG, where ALLCFG = { <G2 | G1> is a CFG and L(G) = }

It is proved that ALLCFG is undecidable, Hence MORECFG is undecidable .

(e) We Assume thet there is a CFG E that decides EMPTYCFG , We’ll use it to get a decider D for ACFG,

Build a CFG G’

G’(x) := if x w reject else sim G(w)” Run E(G’). If E accepts, reject. If rejects, accept.

EMPTYCFG is undecidable

(2) EQCFG is co turing recognizable if its complement is turing recognizable .

Complement of (EQCFG)= A B

A is the set which consists of strigs is easy to recognize , Given As,

A= { w | w not haves the form <G1, G2> for some CFG G1 and G2}

And D is turing machine recognizable, D = { <G1, G2> | G1 and G2 are CFGs and L(G1) is not equal to L(G2) }

Hence if complement of EQCFG is turing recognizable and EQCFG is co turing recognizable.

(3) Consider that R is the decider for language S. <M> ETM waccept of M is not of use. ETM is decided by the decider D as:

D on input x:

1. Run machine R on input <M, waccept>. If R accepts, then accept.

2. If R rejects, then rejects

Hence it proved that ,

S = {<M, w>|M is a TM and w is a useless state in M} is undecidable.

Related Questions

Navigate

• Browse (All)
• Browse 2
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.