GATE 2023 CS Q.24: solution and answer

Official answer: A, C, DSource: Official answer key, GATE 2023 CS (IIT Kanpur)

1. (A) Regular languages are closed under intersection. Build the product DFA of the two machines, and accept when both components accept. TRUE.

2. (B) Context-free languages are not closed under intersection. Take $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\}$. Both are context-free. Their intersection is $\{a^n{b}^n{c}^n\mid n\ge 0\}$, which is not context-free by the pumping lemma for CFLs. FALSE.

3. (C) Recursive languages are closed under intersection. Run the deciders $M_1$ and $M_2$ one after the other on $w$, and accept only if both accept. Both always halt, so the new machine always halts. TRUE.

4. (D) Recursively enumerable languages are closed under intersection. Run $M_1$ and $M_2$ on $w$, one after the other or interleaved, and accept if both accept. If $w$ is in both languages, both machines halt and accept. If not, the new machine need not halt, which is allowed for an RE language. TRUE.

5. Statements A, C and D are correct, and B is the only false one.