The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
+15 votes

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 in Theory of Computation by Veteran (59.4k points)
edited by | 1k views

2 Answers

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

Related questions

Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true

35,487 questions
42,746 answers
42,138 users