2 votes 2 votes closed as a duplicate of: GATE CSE 2012 | Question: 24 CFG is not closed under complementation , but REC is? Theory of Computation theory-of-computation + – h4kr asked Nov 24, 2022 • retagged Dec 28, 2022 by h4kr h4kr 395 views comment Share Follow See 1 comment See all 1 1 comment reply Hira Thakur commented Nov 24, 2022 reply Follow Share GATE CSE 2012 | Question: 24 (Here "Which of the following problems are decidable" is asked) 1 votes 1 votes Please log in or register to add a comment.
Best answer 1 votes 1 votes The given problem is reducible to the halting problem of turning the machine, so UNDECIDABLE. This is an Undecidable problem. (https://cs.stackexchange.com/questions/132411/deciding-whether-complement-of-context-free-language-is-context-free) Not closed does not mean Undecidable.(https://gateoverflow.in/78060/undecidability) C. It’s Trivial. So decidable. D. It’s Trivial. So decidable raja11sep answered Nov 24, 2022 • selected Nov 24, 2022 by h4kr raja11sep comment Share Follow See all 2 Comments See all 2 2 Comments reply Vishal_kumar98 commented Nov 24, 2022 reply Follow Share What do you mean by being trivial? 0 votes 0 votes gatecse commented Nov 24, 2022 reply Follow Share If a property is true for every element of a set or false for every element of a set then it becomes trivial. 0 votes 0 votes Please log in or register to add a comment.