1.6k views

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?

1. $L_1$' is recursive and $L_2$' is recursively enumerable
2. $L_1$' is recursive and $L_2$' is not recursively enumerable
3. $L_1$' and $L_2$' are recursively enumerable
4. $L_1$' is recursively enumerable and $L_2$' is recursive

edited | 1.6k views

$L_1$ being recursive, we have a TM M for $L_1$ which accepts all words in $L_1$ and rejects all words in $L_1$'. So, this TM also works for $L_1$' by changing the accept and reject states. Thus $L_1$' is recursive.

$L_2$ being recursively enumerable but not recursive means TM for $L_2$ can accept all words in $L_2$ but cannot reject all words not in $L_2 \Rightarrow$ TM for $L_2$' cannot exist (as otherwise TM for $L_2$ could simulate the moves of that TM to reject words in $L_2$')  $\Rightarrow L_2$' is not recursively enumerable. So, (B).

by Veteran (431k points)
edited by
+2
RE are not closed under Complement then how we can definitely say that complement of RE is not REC enumerable.
+3
RE set is not closed under complement. So, given a r.e. language we cannot say if its complement is r.e. or not.

But any regular language is also r.e. and complement of a regular language is regular and hence r.e. too. Here, for a particular subset of RE set we say complement is closed.

Similarly in the question, we do not have the general RE set but a subset where the languages are not recursive. For those languages complement is guaranteed not to be r.e. -> reason given in answer.
+2
So recursively enumerable lang which are recursive like reg... complement is also RE.

But RE which are not recursive complement is non RE.

Is this the conclusion?

as we know recursive language are closed under complementation hence L1 is recusrive language so L1' also and it is also  recusrive enumerable language
( all options are still open as all satisfy above property )

recursive enumerable language are not closed under complementation so it may be recursive enumerable language or not
case 1: if L' is  recursive enumerable language
as we know if L and L' are recursive enumerable languages then L is recursive language but here in question they mentioned L2 is not recusrive
hence L2' cant be recursive enumerable language
therfore L2' accept only case 2 which is L2' is not recursive enumerable language

Ans is B

by Active (2.8k points)