1 votes 1 votes Theory of Computation decidability theory-of-computation turing-machine recursive-and-recursively-enumerable-languages + – Na462 asked Nov 14, 2018 Na462 1.6k views answer comment Share Follow See all 22 Comments See all 22 22 Comments reply Hemanth_13 commented Nov 14, 2018 reply Follow Share B? 0 votes 0 votes Manas Mishra commented Nov 14, 2018 reply Follow Share whts the answer ? B ? 0 votes 0 votes Gurdeep Saini commented Nov 14, 2018 reply Follow Share @hemanth explain ?? 0 votes 0 votes Deepanshu commented Nov 14, 2018 i edited by Deepanshu Nov 15, 2018 reply Follow Share i am thinking of b by applying rice theorem 2nd part to 2nd statement . not sure though 0 votes 0 votes Manas Mishra commented Nov 15, 2018 reply Follow Share For L1 , by rice 1st theorem it is non monotonic property so undecidable now using rice 2nd theorem , Tyes ⊆ Tno ..[ let Tyes = {11} and Tno = {1111} ] so its non re For L2 ; by using rice 1st theorem it is non monotonic property so undecidable now For Tyes , if out TM accept anything accept {ε,0.1,00,11} , then we can halt and say yes but for Tno we can't say anything becoz it may happen that when we halt after some step it will accept anything among {ε,0.1,00,11} .. so we are not been able to say no case bt we can say yes case so its semi decidable Thus L2 is semidecidable ...... 0 votes 0 votes Hemanth_13 commented Nov 15, 2018 i edited by Hemanth_13 Nov 15, 2018 reply Follow Share Epsilon is part of L1 so it's not at all RE i.e. it's unable to accept strings in the language But for L2 I'm not getting the language at all I thought it as L1 complement I felt as most of the questions are Partially UD like halting problem this is also Partially decidable. if there is some Turing machine that accepts every string in L and either rejects or loops on every string not in L, then L is Semi-decidable or computably enumerable (CE) Option B What's the answer given @na462 0 votes 0 votes Gurdeep Saini commented Nov 15, 2018 reply Follow Share For L1 , by rice 1st theorem it is non trivial property so undecidable now using rice 2nd theorem , Tyes ⊆ Tno ..[ let Tyes = {11} and Tno = {1111} ] so its non re (@manas) and Epsilon is part of L1 so it's not at all RE i.e. it's unable to accept strings in the language (@hemanth) both explaination right 0 votes 0 votes Gurdeep Saini commented Nov 15, 2018 reply Follow Share L2 is set of turing machine which accept anything but not 00 or 11 or both now we have enumerable method for this so it is semidecideable because explanation lets take an example lets a turing macnine accept 1 than we directly take it lets take an example lets a turing macnine accept 1,10 than we directly take it now take an example lets a turing machine who accept 11 but we are wating whether it accept anything other than 00,11 in this case it may or may not halt @hemanth @manas check it 0 votes 0 votes Hemanth_13 commented Nov 15, 2018 reply Follow Share I have an enumeration method Gurdeep Saini but its non deterministic One TM for languages except epsilon 00 11 --> 0,1,01,10--> It accepts the highlighted 4 strings Other TM for strings >3 So L2 is Partially decidable. 0 votes 0 votes Gurdeep Saini commented Nov 15, 2018 reply Follow Share if a turing macnine accept 11 it does not mean that is accept 1 0 votes 0 votes Hemanth_13 commented Nov 15, 2018 reply Follow Share I'm not getting your point could you please elaborate on this "if a Turing machine accept 11 it does not mean that is accept 1" 0 votes 0 votes Gurdeep Saini commented Nov 15, 2018 reply Follow Share simple thing L2 is set of turing machine which accept anything but not 00 or 11 or both be careful i am not introducing epsilon here because it will create problem and no need to introduce epsilon here now a turing mchine accept anything other than 00 ,11 we directly take that if it so we wait for other string means looping 0 votes 0 votes kumar.dilip commented Nov 15, 2018 reply Follow Share L(TM) is Subset of {00,11}. So, It is a finite and Regular Language. According to the Table. Problem Regular Language DCFL CFL CSL Recursive Language Recursive Enumerable Language L1 ⊆ L2 (Subset problem) Decidable UD UD UD UD So, It is decidable. 2. L(TM) Is not Subset of {00,11}. So we can't say Anything Here It is regular or Not or Finite or Not. So, It is Semi-decidable. 0 votes 0 votes Somoshree Datta 5 commented Nov 15, 2018 reply Follow Share kumar.dilip how is L1 decidable? To be a subset of {00,11}, L(TM) can be any one of these languages: {{ },{00},{11},{00,11}}. So if L(TM) doesnt accept anything, then also the TM belongs to L1. And we already know that deciding whether the language of a TM is empty or not is not recursively enumerable. ALso we can prove this using Rice's second theorem. Tyes={00} and Tno={00,12,13}. As Tyes is a proper subset of Tno, so we can say that this is a non monotonic property and hence is not recursively enumerable. 0 votes 0 votes Hemanth_13 commented Nov 15, 2018 reply Follow Share @gurdeep did you find anything wrong in my approach 0 votes 0 votes kumar.dilip commented Nov 15, 2018 reply Follow Share @Somoshree Datta 5 I will be back to this topic soon. 0 votes 0 votes Gurdeep Saini commented Nov 15, 2018 reply Follow Share @hemanth your first approach for L2 seems to be right but your second approach i am not getting 0 votes 0 votes Hemanth_13 commented Nov 15, 2018 reply Follow Share I use two turing machines to accept the language one TM accepts only 0,1,01,10 , other TM accepts all other strings like 010 100 etc of different lengtjs as we were given "not a subset" operation. The second Turing Machine has the capability to accept all the languages but the enumeration procedure might not halt 0 votes 0 votes Na462 commented Nov 15, 2018 reply Follow Share Sorry for late reply Brothers :) Answer is B 1st one is Non REL and Second one is semidecidable. How i did is : 1st : You can see that there exist a non monotonic property here :: Tyes = {00,11} , Tno = Sigma* and Tyes is a subset of Tno Or The subset of {00,11} contains Phie now to check wether Phie is accepted by TM its undecidable (U can use Rices theorem) 2st: Non trivial Property : Tyes = {0} , Tno = {00,11} and Tyes is not subset of Tno so there exist a non trivial property So its Semidecidable Please tell if something is wrong ? 1 votes 1 votes Gurdeep Saini commented Nov 15, 2018 reply Follow Share @na462 i think uou are right 0 votes 0 votes Somoshree Datta 5 commented Nov 15, 2018 reply Follow Share For L2, by applying Rice's 1st theorem, we can say that L2 is undecidable. But we can apply Rice's 2nd theorem here. So here in order to know if L(tm) is not a subset of {00,11}, we can see if it accepts atleast one string other than 00 and 11..In that case we can halt and say that<TM> belongs to L2 since L(TM) is not a subset of {00,11}. But we can never be sure about the no case of the problem, i.e. whether L(TM) is a subset of {00,11}. So this is semi decidable and RE. Is this approach correct? 0 votes 0 votes Gurdeep Saini commented Nov 18, 2018 reply Follow Share Somoshree Datta 5 yes your approach is right 0 votes 0 votes Please log in or register to add a comment.