Let $L_{1}$ ,be a recursive language,and let $L_{2}$ be a recursively enumerable but not a recursive language.Which one of the following is TRUE?

Open in App

Solution

Given that $L_{1}$ is REC and $L_{2}$ is RE but not REC.
Consider choice (a) $_{1}$ is REC and $_{2}$ is RE.
Since $L_{1}$ is REC,clearly $_{1}$ is also REC.
Since $L_{2}$ is RE but not REC,its complement has to be not RE.
$∴$ But (a) claims that $L_{2}$ is RE.
Therefore (a) is false.
Consider (b) $_{1}$ is REC and $_{2}$ is not RE.
if $L_{1}$ is REC,then $_{1}$ is REC.
Also,if $L_{2}$ is RE but not REC, then $_{2}$ is not RE.
$∴$ (b) is true.
Clearly (c) and (d) false since $_{2}$ is not RE.

Suggest Corrections

Similar questions

¯ Y

¯ X

L_{1} a n d L_{2}

L_{1}

L_{2}

_{1}

L_{1}

_{2}

L_{2}

_{1}

_{1} \cup L_{2}

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