L={ ⟨M⟩ ∣L(M)=Σ∗ }
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
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 Σ∗. Now using N we try to solve non-halting problem as follows:
Explanation :-
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)=Σ∗ 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 Σ∗).
Now, we just give the encoding of A to our assumed TM N. If N says "accept", we have that L(A) is Σ∗ => 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.
In this explanation given if H doesn't halt on w ,L(A) = Σ∗
Sir can u explain if H is not halting how langauge of A is becoming Σ∗......????
