Let L₁ be a recursive language. Let L₂ and L₃ be languages that are recursively enumerable but not recursive. Which of the following statements is not necessarily true? A)L₂ - L₁ is recursively enumerable. B)L₁ - L₃ is recursively enumberable C)L₂ intersection L₁ is recursively enumberable D)L₂ union L₁ is recursively enumberable

Question

Quizplus · Accepted Answer

The difference between a recursive language and a recursively enumerable but not recursive language is not guaranteed to be recursively enumerable. This is because while you can enumerate the elements of the recursive language, you cannot effectively enumerate the non-elements of the recursively enumerable but not recursive language to perform the subtraction.

Let L1 Be a Recursive Language

Let L₁ Be a Recursive Language