GATE 2010 CS (CS1) – Question 27
L₁ is recursive. L₂,L₃ are recursively enumerable but nonrecursive. Which is NOT necessarily true?
Practise this question in The GATE Grind →
Show answer and explanation
Correct answer: (B) L₁−L₃ is recursively enumerable
Explanation
Recursive L₁ has a recursive complement, so L₂−L₁ is RE. RE languages are closed under intersection and union. But with L₁=Σ*, L₁−L₃ is the complement of a nonrecursive RE language, which cannot be RE. Thus B is not guaranteed.