25 votes 25 votes Which the following is FALSE? Complement of a recursive language is recursive. A language recognized by a non-deterministic Turing machine can also be recognized by a deterministic Turing machine. Complement of a context free language can be recognized by a Turing machine. If a language and its complement are both recursively enumerable then it is recursive. Complement of a non-recursive language can never be recognized by any Turing machine. Theory of Computation tifr2014 theory-of-computation closure-property + – makhdoom ghaya asked Nov 20, 2015 • edited May 15, 2018 by Milicevic3306 makhdoom ghaya 7.6k views answer comment Share Follow See all 4 Comments See all 4 4 Comments reply sripo commented Oct 12, 2018 reply Follow Share Why is D incorrect my reasoning is that recursively enumerable languages do not have a complement.So what is the complement of a recursively enumerable language? Isn't Recursively Enumerable superset of Recursive so how does its complement become recursive. Please correct my reasoning,so that this misconception is eliminated. 0 votes 0 votes akash.dinkar12 commented Dec 2, 2018 reply Follow Share @sripo U can use the fact that recursive languages are closed under the compliment and every recursive language is recursively enumerable. If u r saying that if a language and its complement is recursively enumerable, then it means u want to say that Even recursively enumerable languages are closed under complement and if this is true then there will be no difference between recursively enumerable and recursive languages, I mean the same set can represent both languages and So language will become recursive.. 2 votes 2 votes KUSHAGRA गुप्ता commented Dec 6, 2019 reply Follow Share $A:true$ $B:true$ $C:true$ $D:true$ $E:false$ Image for D Note: A language is Recursively enumerable (RE) but not recursive (REC) then it complement is non-RE. 7 votes 7 votes Sanandan commented Oct 6, 2020 reply Follow Share option E is false. 0 votes 0 votes Please log in or register to add a comment.
Best answer 29 votes 29 votes True. For a recursive language, we have a TM which says for any string "w", "yes" if it belongs to the language and "no" if it does not. For the complement of a recursive language we just have to reverse 'yes' and 'no' conditions and this is possible with a slight modification to the original TM. So, the new language is also recursive. True. Non-determinism does not add any recognizing power to a Turing machine though it can affect the time complexity in solving a problem. True. Complement of CFL is recursive. and recursive language is recognized by Turing machine. So, complement of a context free language can be recognized by TM True. If a language is r.e., we have a TM which says "yes" whenever a given string belongs to L. Similarly, if its complement is r.e., we have a TM which says "yes", whenever a string does not belong to the language. So, combining both we can always say "yes" if a string belongs to the language and "no" if a string does not belong to L $\implies$ L is recursive. False. Non-recursive Language can be:- (a) r.e. or (b) Non r.e. As seen in option D, if the language is RE but not recursive, its complement cannot be r.e. (recognized by a TM). But, if the language is not r.e. its complement may be r.e. (which Can be recognized by TM). option E is false. Example:- $L=\{\langle M,w\rangle \mid M \text{ is a TM and it does not halt on string } w\}.$ //Non RE (complement of halting problem) $L^c=\{\langle M,w \rangle \mid M \text{ is a TM and it halts on string } w\}$ //RE but not Recursive //recognized by TM (halting problem) So, answer is (E). srestha answered Nov 20, 2015 • edited Jun 25, 2018 by Arjun srestha comment Share Follow See all 23 Comments See all 23 23 Comments reply Show 20 previous comments Aadesh commented Oct 9, 2020 reply Follow Share @Srivathsa I guess your assumption is wrong; the Turing machine does read epsilon. https://gateoverflow.in/83694/turing-machine 0 votes 0 votes Srivathsa commented Oct 20, 2020 reply Follow Share Thank u very much @Aadesh i did not know that 0 votes 0 votes vishnu_m7 commented Nov 3, 2020 reply Follow Share As seen in option D, if the language is RE but not recursive, its complement cannot be r.e. (recognized by a TM). If language is RE its complement MAY OR MAY NOT be RE should be the correct statement, right? 0 votes 0 votes Please log in or register to add a comment.
0 votes 0 votes According to me Option C and Option E both are false. As TM cannot recognise epsilon, complement of a CFL can have epsilon. Srivathsa answered Jul 22, 2020 Srivathsa comment Share Follow See all 0 reply Please log in or register to add a comment.