GATE CS 2023 Q14 — Regular and Context-free Languages

We analyze the closure properties of the given language families under intersection:

• Option A (Correct): Regular languages are closed under intersection. If $L_1$ and $L_2$ are regular, we can construct a product DFA to accept $L_1 \cap L_2$.
• Option B (Incorrect): Context-free languages (CFLs) are not closed under intersection. For example, $L_1 = \{a^n b^n c^m \mid n, m \ge 0\}$ and $L_2 = \{a^m b^n c^n \mid n, m \ge 0\}$ are both CFLs, but their intersection $L_1 \cap L_2 = \{a^n b^n c^n \mid n \ge 0\}$ is not context-free.
• Option C (Correct): Recursive (decidable) languages are closed under intersection. Given deciders $M_1$ and $M_2$ for two recursive languages, we can construct a decider $M$ that runs $M_1$ on the input, and if it accepts, runs $M_2$. $M$ halts and accepts if and only if both accept.
• Option D (Correct): Recursively enumerable (RE) languages are closed under intersection. Given Turing machines $M_1$ and $M_2$ for two RE languages, we can construct a TM $M$ that runs $M_1$ and $M_2$ in parallel (using interleaving/step-by-step simulation). If both halt and accept, $M$ accepts.