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 (59.9k points) | 1.2k views
Complement of a Recursive language is always Recursive, So option c is false.

2 Answers

+8 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 , if a machine which accepts RE language then there is turing machine so it has three options either accept , reject or loop hence option A is true C is not 

answered by Loyal (8k points)
selected 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
47,910 questions
52,287 answers
67,728 users