GATE 2018 CS Q.7: solution and answer

Official answer: BSource: Official answer key, GATE 2018 CS (IIT Guwahati)

1. Recall the hierarchy: recursive languages $\subset$ recursively enumerable (RE) languages $\subset$ all languages over $\Sigma$.

2. (A) RE languages are not closed under complementation. If both $L$ and $\overline{L}$ were RE, then $L$ would be recursive. Some RE languages are not recursive (for example the language of the halting problem), so their complements are not RE. (A) is false.

3. (B) RE languages are closed under intersection. Given Turing machines $M_1$ and $M_2$ accepting $L_1$ and $L_2$, build a machine that runs $M_1$ on the input and, if it accepts, runs $M_2$ on the same input, and accepts only if both accept. It accepts exactly $L_1\cap L_2$, so the intersection is RE. (B) is true.

4. (C) Every recursive language is RE, and there are RE languages that are not recursive. So RE is not a subset of the recursive languages. (C) is false.

5. (D) Every RE language is accepted by some Turing machine, and each Turing machine can be encoded as a finite string over a finite alphabet. There are only countably many such strings, so there are only countably many RE languages. (D) is false.

6. Only (B) holds.