589 views
2 votes
2 votes
Consider the following languages:

Lne={〈M〉│L(M)≠ф }

Le={〈M〉│L(M)=ф }
where 〈M〉 denotes encoding of a Turning machine M
Then which one of the following is true?
(a) Lne is r.e. but not recursive and Le is not r.e.
(b) Both are not r.e.
(c) Both are recursive
(d) Le is r.e. but not recursive and Lne is not r.e.

1 Answer

1 votes
1 votes

Option A.

L(M)$\neq \phi$ means a turing machine that accepts something. A turing machine can say "YES" if it actually accepts something but if it doesn't then it will loop forever. Thus Lne is RE but not recursive since it does not halt when it doesn't accept any strings.

L(M) $= \phi$ means a TM accepts nothing. This is surely NRE. Since a TM cannot say "YES" or "NO".

So option A.

edited by

Related questions

3 votes
3 votes
2 answers
3
3 votes
3 votes
1 answer
4