GATE CSE 2002 | Question: 2.14

Question

Which of the following is true?

• A. The complement of a recursive language is recursive
• B. The complement of a recursively enumerable language is recursively enumerable
• C. The complement of a recursive language is either recursive or recursively enumerable
• D. The complement of a context-free language is context-free

Comments

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.

---

Option C is more like

L’ is a RE => L’ is REL too

or

L’ is a REL => L’ may or may not be RE => which is is false as it is always RE

Answer 1

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

Comments

Thanks buddy

---

JAINchiNMay

you can remember not closed one’s and rest all are closed ( remembering after taking examples will help).

---

Hi All, incase if the question is multiple select then what options i should select?

Option A and Option C or only option A

Please share your thoughts.

Answer 2

Complement of recursive language is always recursive.

Comments

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

---

@Mk Utkarsh

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

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

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

Answer 3

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.

Answer 4

Option A) is true, The complement of a recursive language is recursive.