+16 votes
1.3k 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
asked
edited | 1.3k views

## 2 Answers

+23 votes
Best answer

$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).

answered by Veteran (408k points)
edited by
+1
RE are not closed under Complement then how we can definitely say that complement of RE is not REC enumerable.
+2
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.
+1
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?
+5 votes

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

answered by Active (2.6k points)
Answer:

+16 votes
2 answers
1
+20 votes
3 answers
2
+15 votes
2 answers
3
+14 votes
2 answers
4
+36 votes
6 answers
5
+14 votes
2 answers
6
+13 votes
1 answer
7