retagged by
2,086 views
3 votes
3 votes
Consider the following Languages:

$L_{ne}=\{\langle M \rangle \mid L(M)\neq \phi \}$

$L_{e}=\{\langle M \rangle \ \mid L(M)=\phi \}$

where $\langle M \rangle$ denotes encoding of a Turing Machine $M$
Then which of the following is true?

(a) $L_{ne}$ is r.e. but not recursive and $L_{e}$ is not r.e.
(b) Both are not r.e.
(c) Both are recursive
(d) $L_{e}$ is r.e. but not recursive and $L_{ne}$ is not r.e.
retagged by

1 Answer

Best answer
14 votes
14 votes

Answer should be A.

$L_{ne}$ says the input encoded TM $M$ should accept a string - language of $M$ is not empty set. i.e., if we get a string which is accepted by $M$ then our work is done - we get an answer for the yes part. But in case we do not get a string we have to check all infinite strings to know finally whether it will be not equal to $\phi$ . Therefore we do not have answer for no part. Hence it is RE but not recursive.

$L_e$ is not even re because we do not have answer for yes part . We have to check all the infinite strings to answer whether it finally accepts $\phi$ .



We can also apply Rice's theorem here. Both $L_{ne}$ and $L_{e}$ describes non-trivial properties of r.e. languages. So, as per Rice's theorem both are undecidable. Now, $L_{e}$ is a non-monotonic property ($L(T_{yes}) \subset L(T_{no})$ possible for empty set and any non-empty set respectively). So, $L_{e}$ is not even r.e. as per Rice's theorem part 2. Rice's theorem part 2 cannot be used for $L_{ne}$ since it is not a non-monotonic property (we cannot get any $T_{yes}, T_{no}$ such that $L(T_{yes} \subset L(T_{no})$. So, we cannot say if it is not r.e. using Rice's theorem and we have to use the first method for this part. 

http://www.gatecse.in/rices-theorem/

edited by

Related questions

0 votes
0 votes
1 answer
2
Deepanshu asked Dec 29, 2018
880 views
L = {<M1, M2>M1 and M2 are two TMs, and ε ∈ L(M1) \ L(M2) }.is it RECURSIVE OR RECURSIVE ENUMERABLE OR NOT EVEN RECURSIVE ENUM.