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

Let L1 be a recursive language, and let L2 be a recursively enumerable but not a recursive language. Which one of the following is TRUE?

  1. L1' is recursive and L2' is recursively enumerable
  2. L1' is recursive and L2' is not recursively enumerable
  3. L1' and L2' are recursively enumerable
  4. L1' is recursively enumerable and L2' is recursive
asked in Theory of Computation by Veteran (69k points)
retagged by | 952 views

2 Answers

+22 votes
Best answer

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

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

answered by Veteran (346k points)
selected 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.3k 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

33,593 questions
40,128 answers
38,389 users