edited by
11,481 views
33 votes
33 votes

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

  1. regular
  2. context-free
  3. context-sensitive
  4. recursive
edited by

5 Answers

Best answer
43 votes
43 votes

(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

edited by
4 votes
4 votes
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
4 votes
4 votes

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

2 votes
2 votes

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

Ans D) Recursive , is correct option.

Answer:

Related questions

33 votes
33 votes
4 answers
1
Kathleen asked Sep 11, 2014
13,855 views
A clustering index is defined on the fields which are of typenon-key and orderingnon-key and non-orderingkey and orderingkey and non-ordering
37 votes
37 votes
8 answers
2
Kathleen asked Sep 11, 2014
17,607 views
What is the maximum size of data that the application layer can pass on to the TCP layer below?Any size$2^{16}$ bytes - size of TCP header$2^{16}$ bytes$1500$ bytes
55 votes
55 votes
8 answers
4
Kathleen asked Oct 9, 2014
31,313 views
The average number of key comparisons required for a successful search for sequential search on $n$ items is$\frac{n}{2}$$\frac{n-1}{2}$$\frac{n+1}{2}$None of the above