Answer : B,C,D
Option A :
“Every subset of a recursively enumerable language is recursive.” : False.
We know that Every language is a subset of $\Sigma^*,$ and $\Sigma^*$ is a recursively enumerable language. (Every regular language is a recursively enumerable language)
Now, consider any Non-recursive language $L.$ $L $ is subset of $\Sigma^*,$ but $L$ is Non-recursive language, So, we can say that the statement “Every subset of a recursively enumerable language is recursive.” is False.
NOTE that : “Set of all recusrive languages” is proper subset of “Set of all recursively enumerable languages”. BUT a particular recursive language Need not be subset of a particular recursively enumerable language.
For example, consider the language $L$ below :
$L = \{ <M> | M \text{ is a Turing machine, } L(M) \text{ is empty} \}$
We know, by Rice Theorem, that $L$ is undecidable, and unrecognizable. i.e. $L$ is Non-recursive as well as Non-RE language.
But $L$ is subset of $\Sigma^*.$
We can prove that “Every infinite language L has a subset S which is undecidable.”
In fact, both the following statements are true :
- Every infinite language L has a subset S which is undecidable.
- Every infinite language L has a subset S which is unrecognizable.
Refer my answer here for proof of these statements : https://gateoverflow.in/357504/Gate-cse-2021-set-2-question-36?state=edit-357698
https://cs.stackexchange.com/questions/102585/is-every-subset-of-a-re-language-also-re-in-general
Option B :
“If a language $L$ and its complement $\overline{L}$ are both recursively enumerable, then $L$ must be recursive.” : True.
Proof :
Let $L$ be a recursively enumerable language such that $\overline{L}$ is also recursively enumerable. By definition of recursively enumerable language, $L$ is accepted by some Turing machine $M_1$, and $\overline{L}$ is accepted by some Turing machine $M_2.$
Note that if a language $S$ is accepted by a Turing machine $N$ then $N$ definitely halts on all the strings in $S.$
Now, consider language $L.$ Take any string $w \in \Sigma^*,$ run $w$ on $M_1,M_2$ in parallel(Or in interleaved fashion), at least one of $M_1$ or $M_2$ will definitely halt on $w.$
If $w \in L$ then $M_1$ will definitely halt on $w.$
If $w \notin L$ then $w \in \overline{L}$, So, $M_2$ will halt on $w.$
So, for any string $w \in \Sigma^*,$ at least one of $M_1$ or $M_2$ will definitely halt, hence, for every string, we can decide whether $w$ belongs to $L$ or $w$ belongs to $\overline{L}.$
Hence, $L$ is recursive.
Complements of Recursive and Recursively Enumerable Languages :
- A recursive language is one that is accepted by a TM that halts on all inputs.
- The complement of a recursive language is recursive.
- If a language L and its complement are RE, then L is recursive.
- A language can be RE but its complement need not be RE.
https://math.stackexchange.com/questions/3624962/is-a-language-l-recursive-if-it-and-its-complement-lc-are-both-recursively
http://www.cs.columbia.edu/~aho/cs3261/Lectures/L15-Diagonalization_Language.html
Option C :
“Complement of a context-free language must be recursive.” : True.
Complement of a context-free language may or maynot be CFL but since every CFL is CSL, and complement of CSL is always CSL.
So, Complement of a context-free language must be CSL, hence, must be recursive.
Option D :
“If $L_1$ and $L_2$ are regular, then $L_1 \cap L_2$ must be deterministic context-free.” : True.
Intersection of two regular languages is a regular language. If $L_1$ and $L_2$ are regular, then $L_1 \cap L_2$ is regular, hence, is deterministic context-free.