GATE CS 2022 Q.23: Decidability, Reducibility and Undecidability

Which of the following statements is/are TRUE?

Every subset of a recursively enumerable language is recursive.

If a language L and its complement $\overline{L}$ are both recursively enumerable, then L must be recursive.

Complement of a context-free language must be recursive.

If L1 and L2 are regular, then $L_1 \cap L_2$ must be deterministic context-free.

Official answer and solution

Solution

Evaluate each language-theoretic statement using standard closure and decidability theorems.

Evaluating each statement:

(A) FALSE: The set of all subsets of $\{0, 1\}^*$ is uncountably infinite, whereas the set of recursive languages is countably infinite. Since $\{0, 1\}^*$ is recursively enumerable (in fact, regular), it has uncountably many subsets that are not even recursively enumerable, let alone recursive.
(B) TRUE: By Post's theorem, if a language $L$ and its complement $\overline{L}$ are both recursively enumerable, then $L$ is recursive (decidable).
(C) TRUE: Every context-free language is decidable (recursive). Since recursive languages are closed under complementation, the complement of any context-free language is recursive.
(D) TRUE: The class of regular languages is closed under intersection, so $L_1 \cap L_2$ is regular. Every regular language is a deterministic context-free language (DCFL).

Final answer

Options (B), (C), (D)

Common trap

Believing subsets inherit decidability from their superset, which is false.

The answer is the one in the official GATE answer key. The solution is this site's own explanation.

GATE questions are the work of the organising institutes. This site is independent and is not affiliated with them.