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

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
+1
this should be best answer
Complement of recursive language is always recursive.
answered by Boss (14.4k points)
edited by
+8
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.

+1
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
0

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

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

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

1
2