GATE CS 2003 Q13 — Undecidability

To determine the nature of the language $L$, we analyze the two possible cases for the mathematical proposition $P = NP$:

• Case 1: If $P = NP$ is true, then $L = (0+1)^*$. Since $(0+1)^*$ is a regular language, it is also a recursive language.
• Case 2: If $P = NP$ is false, then $L = \emptyset$. Since the empty language $\emptyset$ is a regular language, it is also a recursive language.

In either case, $L$ is a regular language, which implies that $L$ is guaranteed to be a recursive language.

Even though we do not currently know which of the two cases holds, the language $L$ itself is fixed and belongs to the class of recursive languages. Our lack of knowledge about whether $P = NP$ does not change the fact that $L$ is mathematically recursive. Therefore, option A is correct.