Question

Which of the following statements is/are TRUE?

• A. Every subset of a recursively enumerable language is recursive.
• B. If a language \( L \) and its complement \( \overline{L} \) are both recursively enumerable, then \( L \) must be recursive.
• C. Complement of a context-free language must be recursive.
• D. If \( L_1 \) and \( L_2 \) are regular, then \( L_1 \cap L_2 \) must be deterministic context-free.

Hint:

Remember that if both a language and its complement are recursively enumerable, then the language must be recursive.

Answer 1

The Correct Option is B, C, D

(A) False. The complement of a recursively enumerable language is not necessarily recursively enumerable, hence not every subset of a recursively enumerable language is recursive.

(B) True. If both a language and its complement are recursively enumerable, it implies that both the language and its complement are decidable (i.e., recursive), so \(L\) must be recursive.

(C) True. The complement of a context-free language is not necessarily context-free, but it must be recursive, as context-free languages are closed under complementation.

(D) True. If \(L_1\) and \(L_2\) are regular, then their intersection is deterministic context-free. This follows from closure properties of regular and deterministic context-free languages.