GATE CS 2022 Q13 — Regular and Context-free Languages

Let us analyze each statement individually to determine its truth value:

• Statement A: Every subset of a recursively enumerable language is recursive. (FALSE)
  Let $\Sigma = \{a\}$. The language $L = \Sigma^*$ is regular, which means it is also recursively enumerable (RE). However, the power set of $\Sigma^*$ is uncountable ($2^{\aleph_0}$), whereas the set of all recursive (decidable) languages is countable (since there are only countably many Turing machines). Therefore, there exist uncountably many subsets of $L$ that are not even recursively enumerable, let alone recursive.


• Statement B: If a language $L$ and its complement $\overline{L}$ are both recursively enumerable, then $L$ must be recursive. (TRUE)
  This is a fundamental theorem in computability theory (Post's Theorem). If both $L$ and $\overline{L}$ are RE, we can construct a decider for $L$ by running the Turing machine for $L$ and the Turing machine for $\overline{L}$ in parallel (interleaved fashion) on any input $x$. Since $x$ must belong to either $L$ or $\overline{L}$, one of the two machines is guaranteed to halt and accept. This makes $L$ decidable (recursive).


• Statement C: Complement of a context-free language must be recursive. (TRUE)
  Every context-free language (CFL) is recursive (decidable). Since the class of recursive languages is closed under complementation, the complement of any recursive language (and hence any CFL) is guaranteed to be recursive.


• Statement D: If $L_1$ and $L_2$ are regular, then $L_1 \cap L_2$ must be deterministic context-free. (TRUE)
  Regular languages are closed under intersection, so $L_1 \cap L_2$ is regular. Since every regular language is also a deterministic context-free language (DCFL), $L_1 \cap L_2$ is indeed a DCFL.