The Gateway to Computer Science Excellence
+9 votes
$L= \{\langle M \rangle\mid L(M) = \Sigma^*\} $

A. $L$ is RE but $L'$ is not RE

B. Both $L$ and  $L'$ are RE

C. $L$ is not RE but $L'$ is  RE

D. Both $L$ and  $L'$ are not RE
in Theory of Computation by
edited by | 1.1k views

2 Answers

+15 votes
Best answer
Yes. Both L and L' are not RE. We can have the same reduction as done for L(M) is infinite.
Lets assume L is RE. So, we have a TM N which will say "yes" if given an encoding of a TM whose language is $\Sigma ^*$. Now using N we try to solve non-halting problem as follows:
A non halting problem is given as follows: Given an encoding of TM <H> and a word w, whether H does not halt on w. That is, we have to decide if H does not halt on w. This problem is proved to be not RE and so no TM can not even say "yes" for "yes" case of the problem.
Now, given a halting problem (<H>, w), we proceed as follows: We make a new TM say A, which on input x, just simulates H on w for |x| steps. If H halts on w, A goes to reject state. Otherwise it accepts. So, $L(A) =\Sigma^*$  if H does not halt on w and L(A) = a finite set if H halts on w. (If H halts in |x| steps for w, any string with length greater than |w|, would certainly be not in L, making L a finite set and hence can never equal $\Sigma^*$). 
Now, we just give the encoding of A to our assumed TM N. If N says "accept", we have that L(A) is $\Sigma^*$ => H does not halt on w => we solved "yes" case of not halting problem, which is not possible. Hence, our initial assumption of L is RE is false. L is not RE.
 Proving L' is not RE is easy.
L' = {<M> | L(M) is not equal to $\Sigma^*$}
L(M) is not equal to $\Sigma^*$ is a non-monotonic property of TM. Because we can take TM $T_{yes}$ with $L(T_{yes})=\phi$ and $T_{no}$ with $L(T_{no})=Σ^*$. Here, $T_{yes}$ satisfies the property (of being not being equal to $\Sigma^*$) and $T_{no}$ does not satisfy that property and $L(T_{yes})⊂L(T_{no})$, making this a non-monotonic property of TM. And hence this becomes not RE as per Rice's theorem second part.
So, both L and L' are not RE making (D) the correct answer.
selected by

@Arjun Sir, Is L' = {<M>| L(M) = ϕ} correct. I mean complement of everything as nothing!

Can anyone explain how L(A) =Σ∗ when H doesn't halt on w......i am not understanding if H doesn't halt on w how L(A) = Σ∗......???
Can we prove $L(M)=\sum^*$ to be NOT RE as, since we cannot have a TM which can even answer yes for the yes case of the problem.
i guess that can be said

this methodology is right no ayush ?
+1 vote
Answer is D

Both the lanuages are not RE

Related questions

Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true
52,345 questions
60,497 answers
95,319 users