in Theory of Computation
27 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
in Theory of Computation


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
I have a confusion with the term 'or' here.

"The complement of a recursive language is either recursive or recursively enumerable"

the above statement has 2 cases:
1>the complement is recursive (so it is recursively enumerable)
2>the complement is not recursive but recursively enumerable.

case 2 is also impled by the statement .which is wrong as we know recursive languages are closed under complememntation.

I think if the option would have had 'and' in place of 'or' then C would have been true.

Subscribe to GO Classes for GATE CSE 2022

4 Answers

29 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

edited by

1 comment

this should be best answer
20 votes
Complement of recursive language is always recursive.
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$?$

0 votes
If a language L and L' are both recursively enumerable then both languages are recursive.

If L is recursive then L' is  also recursive and consequently bothe are Recursively enumerable.
0 votes
Option A) is true, The complement of a recursive language is recursive.

Related questions