GATE CSE 2008 | Question: 13, ISRO2016-36

Question

If $L$ and $\overline{L}$ are recursively enumerable then $L$ is

• A. regular
• B. context-free
• C. context-sensitive
• D. recursive

Comments

Doubt→ why regular is not the answer all regular languages are also closed in complement.

Answer→  L = {a^n b^n C^n} is a CSL, hence it is RE language too as every CSL is RE as per the Chomsky hierarchy.

Complement of L, L' is also CSL as CSL is closed under complement operation. Hence L' is also RE.
Now, see the case, both L and L' are RE, but L is not regular.

---

While attempting this question, I was sure that it is Recursive, CSL and not CFL.
But I got confused with the Option 1, as Regular Languages are also closed under Intersection so option 1 is correct too but it is not CFL.
So, my doubt is that, while attempting this type of question which are based on Closure Properties, do we have to use the Hierarchical approach {Recursive --> CSL ---> CFL ---> Regular} if it fails in between we don't have to check further?
Is it the right approach?
.

---

If you're saying L is CSL, it is wrong. If you're saying L is regular that is also wrong. And on what basis is this question based on closure property?

---

In case we say 'must' or it's a MCQ

answer is only 'd'

But if we say 'may' or it's a MSQ

Apparently, All are correct

Answer 1

There are two theorems which you have to learn in TOC.

1^st ) If L and L’ both are recursively enumerable, then both language must be Recursive.( As Recursive language are subset of Recursive Enumerable Language)

2^nd ) If L is recursive then L’ is also recursive and Consequently both are recursively Enumerable.