in Theory of Computation edited by
816 views
8 votes
8 votes

Can someone please verify my answers on the following given languages?

Please note that RE=Recursive Enumerable, LBA=Linear Bounded Automata, and TM=Turing Machine

  1. $\text{HALT-TM}=\{\langle M,w \rangle \mid M\text{ is a } TM\text{ and } M \text{ halts on input } w\}$ – Undecidable, RE
  2. $\text{E-TM} = \{<M> | M \text{ is a } TM \text{ and } L(M)=\Phi\}$-Undecidable, NOT RE}$
  3. $\text{EN-TM={<M> | M is a TM and L(M)!=$\Phi$} -Undecidable, RE}$
  4. $\text{REGULAR-TM={<M> | M is a TM and L(M) is a regular language} -Undecidable, RE}$
  5. $\text{EQ-TM={<M1, M2> | M1 and M2 are TMs and L(M1)=L(M2)} -Undecidable, RE}$
  6. $\text{A-LBA={<M,w> | M is an LBA that accepts string w} -Decidable}$
  7. $\text{E-LBA={<M> | M is an LBA where L(M)=$\Phi$} -Undecidable, NOT RE}$
  8. $\text{ALL-CFG={<G> | G is a context free grammar and L(G)=$\Sigma^*$} -Undecidable, NOT RE}$
  9. $\text{T={<M> | M is a TM that accepts $w^r$ whenever it accepts w} -Undecidable, RE}$

I am more interested to know which problems are Recursive Enumerable and which are Non-Recursive Enumerable.

in Theory of Computation edited by
816 views

4 Comments

iv and v should be not re

iv > by rice theorem

T yes for ={}

T no for ={a^nb^|n>=0}

Tyes is proper subset of Tno

so it should be not re

(v) {<M>|L(M)=phi} can be reduced to this problem so not re
0
0
yes iv and v are NOT RE languages.
0
0
Is there any procedure to check whether the language is decidable or not / Rec or RE?
0
0
I think (8) should be semi decidable. Please help @arjun sir!
0
0

Please log in or register to answer this question.