37 votes 37 votes Which of the following is true? The complement of a recursive language is recursive The complement of a recursively enumerable language is recursively enumerable The complement of a recursive language is either recursive or recursively enumerable The complement of a context-free language is context-free Theory of Computation gatecse-2002 theory-of-computation easy closure-property + – Kathleen asked Sep 15, 2014 Kathleen 11.6k views answer comment Share Follow See all 6 Comments See all 6 6 Comments reply Show 3 previous comments Gateasp2020 commented May 8, 2019 reply Follow Share Thank you sir 1 votes 1 votes Doraemon commented Nov 11, 2019 reply Follow Share I have a confusion with the term 'or' here. "The complement of a recursive language is either recursive or recursively enumerable" the above statement has 2 cases: 1>the complement is recursive (so it is recursively enumerable) 2>the complement is not recursive but recursively enumerable. case 2 is also impled by the statement .which is wrong as we know recursive languages are closed under complememntation. I think if the option would have had 'and' in place of 'or' then C would have been true. 3 votes 3 votes tusharb commented Jul 20, 2022 reply Follow Share Option C is more like L’ is a RE => L’ is REL too or L’ is a REL => L’ may or may not be RE => which is is false as it is always RE 0 votes 0 votes Please log in or register to add a comment.
0 votes 0 votes Option A is correct complement of recursive language is recursive. Gajanan Purud answered Sep 15, 2023 Gajanan Purud comment Share Follow See all 0 reply Please log in or register to add a comment.
