• retagged by
1,332 views
5 5 votes
Let $A=\{\langle M\rangle \mid M$ is turing machine that halts on all inputs and $L(M)=L'$ for some undecidable language $L'\}$. Then $A$ is ____

a. Regular language
b. Recursive language but not regular
c. Recursively enumerable language but not recursive language
d. Non-recursively enumerable language

1 Answer

Best answer
8 8 votes
$M$ is a Turing machine that halts on all inputs implies L(M) is recursive.

Now, L(M) = L' for some undecidable language L'.

So, this means L(M) is an undecidable language.  But L(M) must be decidable as $M$ is halting on all inputs. So, there cannot be any such $M$ making $A = \emptyset$ which is a regular language.
• selected by
Position:
Show:

Related questions

0 0 votes
0 0 answers
862
862 views
sripo asked Jan 5, 2019
862 views
As per the given solution,B should be the correct answer right why is D given as the correct answer as the machine accepts atleast one b.
0 0 votes
1 1 answer
450
450 views
Lovejeet Singh asked Oct 30, 2018
450 views
What is the meaning of non trivial property related to a language. Please explain with an example.
1 1 vote
1 1 answer
1.3k
1.3k views
just_bhavana asked Jan 1, 2018
1,300 views
If L is accepted by TM, which halts on every string over alphabet {a, b}, then L′ is recursive language.True or False ?I think false because L′ = TM halts on no string in...
0 0 votes
0 0 answers
1.0k
1.0k views
Shubham Kumar Gupta asked Dec 23, 2017
1,047 views
A. L is undecidableB. L is decidableC. L is regular.D. None of these.Please explain in detail.