Project ForgeTheory of Computation
Grammars, Turing Machines & Decidability
GATE 2008
Medium
If L and L̄ (its complement) are both recursively enumerable, then L is
- Aregular
- Bcontext-free
- Ccontext-sensitive
- recursive
Explanation
This is a classic theorem: a language is recursive if and only if both it and its complement are recursively enumerable — running both semi-deciding procedures in parallel is guaranteed to halt on one of them for any input, giving a full decision procedure.
Source: GATE CS 2008 (2008)
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.