24 votes 24 votes Which of the following statements is TRUE? Every turning machine recognizable language is recursive. The complement of every recursively enumerable language is recursively enumerable. The complement of a recursive language is recursively enumerable. The complement of a context-free language is context-free. The set of turning machines which do not halt on empty input forms a recursively enumerable set. Theory of Computation tifr2012 theory-of-computation recursive-and-recursively-enumerable-languages + – makhdoom ghaya asked Nov 2, 2015 edited May 15, 2018 by Milicevic3306 makhdoom ghaya 2.8k views answer comment Share Follow See all 0 reply Please log in or register to add a comment.
Best answer 22 votes 22 votes False. Turing recognizable language are recursive enumerable and recursive set is a proper subset of it. False, Complement of r.e. need not be r.e. True. Complement of recursive language is recursive and every recursive language is recursive enumerable. False. Complement of CFL need not be CFL (but is guaranteed to be a CSL). False. We cannot make a Turing machine to determine if a given Turing machine does not halt on empty string (for that matter any string). But the complement of this is r.e. (of course not recursive) srestha answered Nov 2, 2015 edited Nov 1, 2018 by Arjun srestha comment Share Follow See all 7 Comments See all 7 7 Comments reply Show 4 previous comments sudsho commented Nov 17, 2016 reply Follow Share Every turning machine recognizable language is recursive enumerable...not recursive(tighest bound or closest answer)...its like type 0 grammars are recursive enumerable not recursive at first place....closest bound... 1 votes 1 votes Jai Kataria commented Sep 26, 2017 reply Follow Share @arjun Sir,option e Not halt on empty input why yes is difficult(as empty input is of length 0) Unable to do such question 0 votes 0 votes shubham shende commented Sep 4, 2019 reply Follow Share How compliment of e option is RE Tyes for phi Tno for €* Tyes is subset of Tno Not RE 0 votes 0 votes Please log in or register to add a comment.
5 votes 5 votes For option e) Say L = {turning machines which do not halt on empty input} So L' = {turning machines which halt on empty input} See L' is REL but not Recursive. So L = (L')' is out of REL circle. hence option e) is false. Pritam Dutta answered Dec 15, 2017 Pritam Dutta comment Share Follow See all 0 reply Please log in or register to add a comment.