The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
x
+20 votes
927 views

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

2 Answers

+19 votes
Best answer
Complement of recursive language is always recursive.
answered by Boss (14.3k points)
edited by
+6
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.
+2
Technically C is also correct.
+1

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

+1
i think A and C both are correct. but strong is option A..
0
I got confused between option A and C too .... how do I decide which is stronger?
+3
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.
0
@arjun sir please explain how c is logically correct.
0

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

0

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

+5 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 Loyal (6.7k points)
+1
this should be best answer


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

39,828 questions
46,802 answers
140,988 comments
58,945 users