edited by
819 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.

edited by

Please log in or register to answer this question.

Related questions

2 votes
2 votes
1 answer
1
Na462 asked Sep 2, 2018
829 views
3 votes
3 votes
1 answer
2
Utkarsh Anand asked Jul 31, 2017
1,401 views
Are Turing decidable languages are closed under Complementation, Reversal, Homomorphism, Inverse Homomorphism and Substitution?
1 votes
1 votes
2 answers
3
0 votes
0 votes
0 answers
4