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

Which of the following is true?

  1. The complement of a recursive language is recursive
  2. The complement of a recursively enumerable language is recursively enumerable
  3. The complement of a recursive language is either recursive or recursively enumerable
  4. The complement of a context-free language is context-free
asked in Theory of Computation by Veteran (52.1k points) | 1.3k views
Complement of a Recursive language is always Recursive, So option c is false.

@Arjun @Digvijay Pandey @Bikram sir,

 In option C,  The Complement of a recursive language is recursive language ...its 100% right.

  but In venn diagram relation between REC and RE ,     REC is comes under to RE , if language is REC then its RE also ....its also true { plz explain where i wrong)

why option C is wrong??

You can see the answer now.
Thank you sir

2 Answers

+9 votes
Best answer

When a language is Recursive then there is a Total Turing machine means a Turing machine which have only two options either accept or rejects so if we complement a recursive language it works according to second figures hence it is recursive too. 

For a recursively enumerable language there is Turing machine and so it has three options either accept, reject or loop. Hence its complement can be either recursively enumerable or not even recursively enumerable.

Among the options A is the best one though C is also not wrong as it includes the statement of A in an either clause. 

Best Option: A

answered by Boss (10.6k points)
edited by
this should be best answer
+19 votes
Complement of recursive language is always recursive.
answered by Boss (14.4k points)
edited by
L is recursive means TM for L accepts all words in L and rejects all words not in L.So, just by changing the accept to reject and vice verse we get a TM for L'. Thus L' must also be recursive.
Technically C is also correct.

@kjdcoswesmvo yes, i think so! C is technically correct 

i think A and C both are correct. but strong is option A..
I got confused between option A and C too .... how do I decide which is stronger?
How's C true? Then only stronger comes to picture. As long as there exists a language which is recursively enumerable and its complement not being recursively enumerable C is false.
@arjun sir please explain how c is logically correct.

I think option C would have been true if in option they mention recursive AND recursive enumerable.


 If L is recursively enumerable, then the complement of L is recursively enumerable if and only if L is also recursive.

Either A or B means $A \oplus B$

so option C is means

"The complement of a recursive language is recursive or recursively enumerable but not both"

That's obviously not true


How you decide Either $A$ or $B$ means $A\oplus B?$

and $A$ or $B$ means $A+B?$

can you explain option $(C)$ please$?$


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
49,811 questions
54,533 answers
75,562 users