GATE 2022 CS Q.23: solution and answer

Official answer: B, C, DSource: Official answer key, GATE 2022 CS (IIT Kharagpur)

1. (A) Take $L={\Sigma }^{\ast }$, which is recursive and hence recursively enumerable. Every language over $\Sigma$ is a subset of ${\Sigma }^{\ast }$. There are uncountably many languages over $\Sigma$ but only countably many Turing machines, so some subset of ${\Sigma }^{\ast }$ is not even recursively enumerable, let alone recursive. (A) is false.

2. (B) Let $M_1$ accept $L$ and $M_2$ accept $\overline{L}$. On input $w$, run $M_1$ and $M_2$ alternately, one step at a time. Every string lies in exactly one of $L$ and $\overline{L}$, so exactly one of the two machines eventually accepts. If $M_1$ accepts, accept $w$. If $M_2$ accepts, reject $w$. This machine halts on every input and decides $L$, so $L$ is recursive. (B) is true.

3. (C) Every context-free language is decidable, for example by the CYK algorithm on a grammar in Chomsky normal form, which always halts. Swapping the accept and reject outcomes of this decider gives a decider for the complement. So the complement of a context-free language is recursive, even though it need not be context-free. (C) is true.

4. (D) Regular languages are closed under intersection, so $L_1\cap L_2$ is regular. A DFA is a deterministic pushdown automaton that never uses its stack, so every regular language is deterministic context-free. (D) is true.

5. Correct options: B, C and D.