GATE 2012 CS (CS1) – Question 34
Which problems are decidable? 1: Does an arbitrary program ever output anything? 2: Given a CFL L, is $\overline L$ context-free? 3: Given regular L, is $\overline L$ regular? 4: Given recursive L, is $\overline L$ recursive?
Practise this question in The GATE Grind →
Show answer and explanation
Correct answer: (D) 3,4
Explanation
Problem 1 is undecidable by reduction from halting. Whether a CFL’s complement is context-free is not generally decidable. Regular and recursive languages are each closed under complement, so 3 and 4 always have answer yes and are decidable. Thus D. The complement bars are essential to the source question.