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

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

---

All are correct, move on. Save time

---

If the Ques is MSQ then mark all, if it's MCQ then mark Recursive because you know what the question maker wants to ask in this question if you have solved enough questions.

Answer 1

(D) recursive

$L$ is recursively enumerable means a $TM$ accepts all strings in $L. \overline{L}$ is recursively enumerable means a $\text{TM}$ accepts all strings in $\overline{L}$. So, we can always decide if a string is in $L$ or not, making $L$ recursive.

http://goo.gl/RtV8MO

Comments

Abhrajyoti00

Thanks , got it!

if it was an msq then all options are correct right?

---

@Pranavpurkar No. Because we are sure that it is REC. But we are not sure whether they are Reg, CFL or CSL.

But if it is REC, it is definitely RE.

---

Abhrajyoti00

but it can be reg,cfl or csl and still both $L$ and $\overline{L}$ will be REL.

Answer 2

as @Manu Thakur said

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 neither regular nor CFL.

 

Now if the question is "If L and L' are recursively enumerable then L is definitely"      

then answer is option D 

 

but if it is "If L and L' are recursively enumerable then L  may be" 

then answer is ALL OF THESE

Comments

great explanation! simple & precise

Answer 3

See folks I was also confused at first but now its cleared, lets see how

We all know why option d is correct since recursive lang is closed under complementation and hence L' is also Recursive lang therefore L' is RE lang also

 

BUT what if the language is regular lang. , if L is regular that means its CFL also but CFL's complementation property is not closed right? therefore L' is not CFL and hence not Rec. lang and hence not RE lang.

 

but you may argue that if L is regular and we first check if its L' is regular or not and since its regular therefore L' is CFL hence CSL and hence recursive and hence RE lang.  but thats not the procedure first we need to go up till the position we can in the language itself till complementation property gets violated like we went up from regular to CFL and there complementation property got violated and hence we became sure ok this will not be our answer.

 

now you may again argue then why did we not go from recursive lang. to RE lang. ,its because in the question its mentioned L is RE lang as well as L' is RE lang.

 

Hope I could clear it a bit

Answer 4

Recursively enumerable language is NOT Closed under complementation where as Recursive lang is Closed Under complementation .

Ans D) Recursive , is correct option.

Comments

@warrior though your answer is correct but logic is incorrect!

---

@ Manu Thakur The logic is simple, If L is recursively enumerable, then the complement of L is recursively enumerable if and only if L is also recursive.For proof just see the best ans.Actually, this is one of the best methods to differentiate (or to check whether the lang is rec or rel) B/w Recursive language and Recursively Enumerable language.

---

" as every CSL is RE as per the Chomsky hierarchy. " isn't it the other way around
Every CSL is regular

Answer 5

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. 

Answer 6

The correct answer is D. recursive.

This is a fundamental theorem in computability theory, often known as Post's Theorem.

 

Explanation

 

Here is the reasoning behind this rule:

1. Recursive (Decidable): A language $L$ is recursive if there exists a Turing machine (a decider) that is guaranteed to halt on every input and give a correct "YES" (accept) or "NO" (reject) answer.

2. Recursively Enumerable (RE): A language $L$ is RE if there is a Turing machine that will halt and say "YES" for strings in $L$. However, for strings not in $L$, it might loop forever. We can only guarantee a "YES" answer.

The Proof:

We are given that both $L$ and its complement $\bar{L}$ are RE. This means we have two Turing machines:

• $M_1$, which is guaranteed to halt and accept any string in $L$.

• $M_2$, which is guaranteed to halt and accept any string in $\bar{L}$.

We can use these two machines to build a new Turing machine, $M_{\text{decider}}$, that decides $L$ (and is guaranteed to halt), proving $L$ is recursive.

Algorithm for $M_{\text{decider}}$ on input $w$:

1. Run both $M_1$ and $M_2$ in parallel (for example, by alternating one step of each machine).

2. Since every string $w$ must be in either $L$ or $\bar{L}$, one of the two machines ($M_1$ or $M_2$) is guaranteed to eventually halt and accept.

3. If $M_1$ halts and accepts, $M_{\text{decider}}$ halts and accepts (because $w \in L$).

4. If $M_2$ halts and accepts, $M_{\text{decider}}$ halts and rejects (because $w \in \bar{L}$).

Because this new machine, $M_{\text{decider}}$, is guaranteed to halt on every input, $L$ is recursive. The other options (A, B, C) are all subsets of recursive languages, but "recursive" is the most general and correct property guaranteed by the premise.