The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
+16 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 (68.8k points) | 652 views

2 Answers

+18 votes
Best answer
Complement of recursive language is always recursive
answered by Veteran (14k points)
selected 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.

+2 votes

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 Boss (9.6k points)

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

32,443 questions
39,188 answers
36,563 users