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

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??

0
You can see the answer now.
0
Thank you sir

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
Complement of recursive language is always recursive.
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
3
4
5
6