Let L₁be a recursive language. Let L₂ and L₃ be language that are recursively enumerable but not recursive. Which of the following statements is not necessarily true?

Open in App

Solution

Given, L₁ is REC and L₂ and L₃ are RE but not REC.
Choice (a)
L₂ - L₁= L₂∩ $(L_{1})^{c}$
= (RE but not REC) $\cap (R E C)^{c}$
= (RE but not REC) $\cap (R E C)$
= $R E \cap R E C = R E \cap R E = R E$
Choice (a) is true.
Choice (b):
L₁ - L₃= L₁∩ $(L_{3})^{c}$
=REC $\cap (R E b u t n o t R E C)^{c}$
Now the complement of a RE but not REC language has to be "not RE".
$∴ L_{1} - L_{3} = R E C \cap n o t R E = n o t R E$
$∴$ Choice (b) is false.
Choice (c):
$L_{2} \cap L_{3}$ = (RE but not REC) $\cap$ (RE but not REC)
= $R E \cap R E = R E$
So, choice (c) is true.
Choice (d):
$L_{2} \cup L_{3}$ = (RE but not REC) $\cup$ (RE but not REC)
= $R E \cup R E = R E$
$∴ C h o i c e (d) i s t r u e .$

Suggest Corrections

Similar questions

L_{1}

L_{2}

L_{1} a n d L_{2}

L_{1}

L_{2}

_{1}

L_{1}

_{2}

L_{2}

_{1}

_{1} \cup L_{2}

¯ Y

¯ X

L_{1} : R e g u l a r, L_{2} : C o n t e x t - f r e e, L_{3} : R e c u r s i v e, L_{4} : R e c u r s i v e l y e n u m e r a b l e .

_{3} \cup L_{4}

_{2} \cup L_{3}

_{1} \cap L_{2}

L_{1} \cup_{2}

Join BYJU'S Learning Program