2 votes 2 votes Consider the following languages: L1={0^(2k)│k≥0} L2={b∈{0,1}*│b∈L(Mb] ) } Which of the above languages is TM recognizable? please explain second one Theory of Computation theory-of-computation + – Akriti sood asked Jan 23, 2017 Akriti sood 498 views answer comment Share Follow See all 7 Comments See all 7 7 Comments reply Sushant Gokhale commented Jan 24, 2017 reply Follow Share Now, L(M) = { $\epsilon$ } or L(M) = {0} or L(M) = {1} and so on(i.e M will be turing machine for each of the strings of (0+1)* ). Now, this is non-trivial and hence, undecidable. Considering extended Rice theorem also, you dont get any voilation. So, I think this is RE. But, I am not sure of this. 0 votes 0 votes Sushant Gokhale commented Jan 24, 2017 reply Follow Share is first one RE? 0 votes 0 votes Akriti sood commented Jan 24, 2017 reply Follow Share first one is given as R.E ND SECOND ONE IS GIVEN AS NON-r.e WHAT IS THE MENAING OF SECOND ONE?? 0 votes 0 votes Rahul Jain25 commented Jan 24, 2017 reply Follow Share First one is CSL so it should be recursive. 0 votes 0 votes Akriti sood commented Jan 24, 2017 reply Follow Share @rahul,can you pls explain second language? 0 votes 0 votes mohit chawla commented Jan 24, 2017 reply Follow Share @akriti, i guess 2nd one is in set form b is set of strings over all possible strings such that string belong to language accepted by T.M Mb. i may be wrong on the interpretation, but 2nd one is quite confusing 0 votes 0 votes Rahul Jain25 commented Jan 24, 2017 reply Follow Share Actually I am not able to understand, but I think they want to say that if a string is accpetable by TM in {0,1}* then it belongs to L2. L2 may be CSL it may be CFL or regular 0 votes 0 votes Please log in or register to add a comment.