Let L1 be a recursive language. Let L2 and L3 be languages that are…
2010
Let L1 be a recursive language. Let L2 and L3 be languages that are recursively enumerable but not recursive. Which of the following statements is not necessarily true?
- A.
L2 – L1 is recursively enumerable
- B.
L1 – L3 is recursively enumerable
- C.
L2 ∩ L1 is recursively enumerable
- D.
L2 ∪ L1 is recursively enumerable
Attempted by 63 students.
Show answer & explanation
Correct answer: B
Answer: The statement "L1 – L3 is recursively enumerable" is not necessarily true.
Key reason: L1 – L3 = L1 ∩ (complement of L3). While L1 is recursive, complement of an r.e. language need not be r.e., so the intersection need not be r.e.
Concrete counterexample: let L1 = Σ* (recursive) and let L3 be the halting set K (r.e. but not recursive). Then L1 – L3 = Σ* − K = complement(K), which is not r.e.
This shows L1 – L3 need not be r.e., so the statement is not guaranteed.
A video solution is available for this question — log in and enroll to watch it.