Question:medium

Which of the following statements is/are TRUE?

Show Hint

Remember that if both a language and its complement are recursively enumerable, then the language must be recursive.
Updated On: Jan 30, 2026
  • Every subset of a recursively enumerable language is recursive.
  • If a language \( L \) and its complement \( \overline{L} \) are both recursively enumerable, then \( L \) must be recursive.
  • Complement of a context-free language must be recursive.
  • If \( L_1 \) and \( L_2 \) are regular, then \( L_1 \cap L_2 \) must be deterministic context-free.
Show Solution

The Correct Option is B, C, D

Solution and Explanation

Let us examine each statement carefully using standard results from automata and computability theory.

(A) False.
A recursively enumerable (r.e.) language need not have a recursively enumerable complement. Since recursive (decidable) languages are exactly those whose language and complement are both r.e., it follows that not every subset of an r.e. language is recursive. Hence, the statement is false.

(B) True.
If a language \( L \) and its complement \( \overline{L} \) are both recursively enumerable, then there exist Turing machines that semi-decide both. This implies that membership in \( L \) can be decided by running both machines in parallel and accepting whichever halts first. Therefore, \( L \) is recursive. Hence, this statement is true.

(C) True.
Although context-free languages are not closed under complementation, every context-free language is decidable (recursive). Since recursive languages are closed under complementation, the complement of a context-free language must be recursive, even though it may not be context-free. Thus, the statement is true.

(D) True.
Regular languages are closed under intersection. Moreover, every regular language is also deterministic context-free (DCFL). Since the intersection of two regular languages is regular, it is also deterministic context-free. Therefore, this statement is true.

Final Answer:
The correct statements are (B), (C), and (D).
Was this answer helpful?
0