1 votes 1 votes Does the statement given below is true? If a language L is recursive enumerable than there does not exits a TM that could accept complement of L but reject L. Theory of Computation theory-of-computation decidability recursive-and-recursively-enumerable-languages turing-machine + – Ayan21 asked Dec 17, 2018 Ayan21 588 views answer comment Share Follow See all 4 Comments See all 4 4 Comments reply kumar.dilip commented Dec 17, 2018 reply Follow Share RELs are not closed under the complementation. So, we don't what will be the language, it may be out RE language. If L is REL, we don't it will reject or not it may go in the infinite loop. 0 votes 0 votes rballiwal commented Dec 17, 2018 reply Follow Share yeah the statement is true, 0 votes 0 votes Shaik Masthan commented Dec 17, 2018 reply Follow Share if L is REL but not RE, then only given statement is true. 0 votes 0 votes Gurdeep Saini commented Dec 25, 2018 reply Follow Share i think the given statement is false because it the statement does not satisfy all condition then we say it is false. statement will be true if it is given language is RE but not recursive 0 votes 0 votes Please log in or register to add a comment.
0 votes 0 votes Because RE languages aren’t closed under complementation. Thus if for L’ there doesnot exist turing machine as the language becomes undecidable .The same machine will reject RE language L and then halt. Thus the above mentioned statement is true. rish1602 answered Jun 24, 2021 edited Sep 4, 2021 by rish1602 rish1602 comment Share Follow See all 0 reply Please log in or register to add a comment.