The Gateway to Computer Science Excellence
+20 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
in Theory of Computation by Veteran (52.2k points)
edited by | 1.6k views

2 Answers

+28 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). 

by Veteran (431k 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?
+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 


by Active (2.8k 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
50,737 questions
57,366 answers
105,265 users