GATE CS 2018 Q7 — Regular and Context-free Languages

Let us analyze each option regarding the set of all recursively enumerable (RE) languages:

• Option A: Closed under complementation (Incorrect)
  The class of RE languages is not closed under complementation. For example, the halting problem language $L_H$ is recursively enumerable, but its complement $\overline{L_H}$ is not recursively enumerable.
• Option B: Closed under intersection (Correct)
  If $L_1$ and $L_2$ are RE languages, there exist Turing machines $M_1$ and $M_2$ that recognize them, respectively. We can construct a machine $M$ for $L_1 \cap L_2$ that runs $M_1$ and $M_2$ on the input string $w$ (either sequentially or in parallel). If both $M_1$ and $M_2$ halt and accept, then $M$ accepts. Thus, $L_1 \cap L_2$ is also recursively enumerable.
• Option C: A subset of the set of all recursive languages (Incorrect)
  Every recursive language is recursively enumerable, but the converse is not true (e.g., the halting problem is RE but not recursive). Therefore, the set of recursive languages is a proper subset of the set of RE languages, not vice versa.
• Option D: An uncountable set (Incorrect)
  Every RE language is recognized by at least one Turing machine. Since any Turing machine can be represented as a finite string over a finite alphabet, the set of all Turing machines is countably infinite. Consequently, the set of all RE languages is countable.