Recursive Language Practice Questions

Let's analyze each statement:
(A) "Every subset of a recursively enumerable language is recursive." This is FALSE. The class of recursively enumerable (RE) languages is closed under subset, but a subset of an RE language can be non-RE, or RE but not recursive. For example, the complement of an RE language is a subset of $\Sigma^*$, but is not necessarily RE, let alone recursive. A simple example is $L_u$ (Halting Problem), which is RE but not recursive. Its complement $\bar{L_u}$ is not RE. $\bar{L_u}$ is a subset of $\Sigma^*$, and $\Sigma^*$ is recursive. But $\bar{L_u}$ is not recursive. So this statement is false.

(B) "If a language L and its complement $\bar{L}$ are both recursively enumerable, then L must be recursive." This is TRUE. This is a well-known theorem in computability theory. A language is recursive if and only if both the language and its complement are recursively enumerable.

(C) "Complement of a context-free language must be recursive." This is TRUE. Context-Free Languages (CFLs) are a proper subset of Recursive Languages. Recursive languages are closed under complementation. Since every CFL is recursive, its complement is also recursive. Also, the complement of a CFL is a Context-Sensitive Language (CSL), and CSLs are recursive.

(D) "If $L_1$ and $L_2$ are regular, then $L_1 \cap L_2$ must be deterministic context-free." This is TRUE. Regular languages are closed under intersection. If $L_1$ and $L_2$ are regular, then $L_1 \cap L_2$ is also regular. Every regular language is a deterministic context-free language (DCFL). Therefore, $L_1 \cap L_2$ must be deterministic context-free.

The solution indicates (b, c, d) as TRUE.

The problem asks to identify which language is NOT recursive.
The language $L = \{ \langle M \rangle \mid M \text{ is a PDA such that } L(M)=\Sigma ^ * \}$ represents the completeness problem for Context-Free Languages (CFLs).
The completeness problem for CFLs (i.e., whether a PDA accepts all strings $\Sigma^*$) is known to be undecidable.
Since a language is recursive if and only if it is decidable, an undecidable language is not recursive.
Therefore, this language is not recursive.

Recursively enumerable (RE) languages are closed under operations like union and intersection. However, they are not closed under complementation. The set of recursive languages is a proper subset of the set of RE languages. Furthermore, the set of all RE languages is countably infinite because they can be enumerated by Turing machines, and the set of all Turing machines is countable.

We are given that X is a recursive (REC) language, and Y is recursively enumerable (RE) but not REC.
From the reduction $Z \le_m \bar{X}$: Since X is REC, its complement $\bar{X}$ is also REC. A language that reduces to a REC language must also be REC. Therefore, Z is recursive.
From the reduction $\bar{Y} \le_m W$: Since Y is RE but not REC, its complement $\bar{Y}$ is not RE. If W were RE, then $\bar{Y}$ would also have to be RE, which is a contradiction. Therefore, W is not recursively enumerable.

A language $L$ is recursive if and only if both $L$ and its complement $\bar{L}$ are recursively enumerable (r.e.). This is a fundamental property of recursive languages.

Let's analyze the given options:
A. If neither $L$ nor $\bar{L}$ is r.e., this is a viable possibility. For example, some undecidable languages and their complements might not be r.e.
B. If $L$ is r.e. but not recursive, then its complement $\bar{L}$ cannot be r.e. (otherwise $L$ would be recursive). Thus, $\bar{L}$ is not r.e. This is a viable possibility.
C. If both $L$ and $\bar{L}$ are r.e., then by the property mentioned above, $L$ must be recursive. Therefore, it is NOT possible for both $L$ and $\bar{L}$ to be r.e. but not recursive.
D. If both $L$ and $\bar{L}$ are recursive, this is a viable possibility. Any recursive language has a recursive complement.

Therefore, the statement that is NOT a viable possibility is when both $L$ and $\bar{L}$ are recursively enumerable but not recursive.

The final answer is $\boxed{C}$

This question tests the closure properties of language classes. Let's analyze each option:

• Recursive (REC) languages are a subset of Recursively Enumerable (RE) languages.
• REC languages are closed under union, intersection, complement, and set difference.
• RE languages are closed under union and intersection, but not under complement or set difference.

Let's examine the statements:

• A. L2 - L1 is recursively enumerable: The set difference L2 - L1 can be written as L2 ∩ L1'. Since L1 is REC, its complement L1' is also REC. The intersection of an RE language (L2) and a REC language (L1') is always RE. Thus, this statement is necessarily true.

• C. L2 ∪ L1 is recursively enumerable: Since L1 is REC, it is also RE. The union of two RE languages (L2 and L1) is always RE. Thus, this statement is necessarily true.

• D. L2 ∩ L1 is recursively enumerable: The intersection of an RE language (L2) and a REC language (L1) is always RE. Thus, this statement is necessarily true.

• B. L1 - L3 is recursively enumerable: This set difference is L1 ∩ L3'. We are given that L3 is RE but not REC. A key property is that if a language is RE but not REC, its complement (L3') is not RE. Therefore, L1 ∩ L3' is the intersection of a REC language and a non-RE language. This operation is not guaranteed to produce an RE language. For example, if L3 is the Halting Problem, then L3' is not RE. So, L1 - L3 is not necessarily RE.

Therefore, the statement that is not necessarily true is B.

The totality problem for Turing Machines (whether a TM accepts all strings) is undecidable (and not even recursively enumerable).