Which of the following statements is/are TRUE?

Answer: The true statements are those about a language whose complement is also r.e., the complement of a context-free language, and the intersection of two regular languages.

• Every subset of a recursively enumerable language is recursive. — False. Counterexample: Σ* is recursively enumerable, and it contains subsets that are not recursive (for example, the halting set is r.e. but not recursive). Thus a subset of an r.e. language need not be recursive.

• If a language L and its complement L’ are both recursively enumerable, then L must be recursive. — True. Decide membership by simulating the recognizers for L and for its complement in parallel (dovetailing). One recognizer will eventually accept, so you can halt with the correct yes/no answer. Therefore L is decidable (recursive).

• Complement of a context-free language must be recursive. — True. Every context-free language is decidable (e.g., via the CYK algorithm or other parsing algorithms), so it is recursive. Recursive languages are closed under complement, so the complement is also recursive.

• If L1 and L2 are regular, then L1 ∩ L2 must be deterministic context-free. — True. The intersection of two regular languages is regular. Every regular language can be recognized by a deterministic pushdown automaton (the DPDA can simply ignore its stack), so every regular language is deterministic context-free. Hence the intersection is deterministic context-free.

Conclusion: The three true statements are the ones about a language and its complement both being r.e., the complement of a context-free language, and the intersection of two regular languages.