Project ForgeWhich of the following problems are decidable?
1) Does a given program ever produce an output? 2) If L is a context-free language, then is L̄ (its complement) also context-free? 3) If L is a regular language, then is L̄ also regular? 4) If L is a recursive language, then is L̄ also recursive?
- A1, 2, 3, 4
- B1, 2
- C2, 3, 4
- 3, 4
Explanation
(1) is the halting/output problem — undecidable in general. (2) asks about an arbitrary CFL's complement being context-free, which isn't decidable to verify in general (CFLs aren't closed under complement, and testing membership in that closed subclass is undecidable). (3) and (4) are ALWAYS true as mathematical facts — regular languages and recursive languages are both closed under complementation — so an algorithm can simply always answer 'yes' for these, making them trivially decidable. So only 3 and 4 are decidable.
Source: GATE CS 2012 (2012)
This question is part of a 15-day revision cycle — sign in and Project Forge will bring it back the day before you'd forget it.