Project ForgeTheory of Computation
Grammars, Turing Machines & Decidability
GATE 2014
Hard
Let L be a language and L̄ be its complement. Which one of the following is NOT a viable possibility?
- ANeither L nor L̄ is recursively enumerable (r.e.).
- BOne of L and L̄ is r.e. but not recursive; the other is not r.e.
- Both L and L̄ are r.e. but not recursive.
- DBoth L and L̄ are recursive.
Explanation
A classical theorem states: if BOTH a language and its complement are recursively enumerable, then the language must be RECURSIVE (decidable). So 'both L and L̄ are r.e. but NOT recursive' is a logical contradiction and thus not a viable possibility.
Source: GATE CS 2014 (Session 1) (2014)
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.