The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
x
+16 votes
2.8k views

If $L$ and $\bar L$ are recursively enumerable then $L$ is

  1. regular
  2. context-free
  3. context-sensitive
  4. recursive
asked in Theory of Computation by Veteran (59.4k points)
retagged by | 2.8k views

2 Answers

+26 votes
Best answer

(D) recursive

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


http://goo.gl/RtV8MO

answered by Loyal (6.1k points)
edited by
0
Let say if L is regular then L(complement) is also regular then both are RE.???

also if L is CFG then L(complement) is recursive(as CFG are not closed under complementation) then also both will be RE.???

same with CSG and recursive

Then why not all option is correct?

Plz explain
+2
@Hitesh
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.
+1 vote

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

Ans D) Recursive , is correct option.

answered by Loyal (6.2k points)
+2
why regular is not the answer all regular languages arealso closed in complement.
+2
@phelps 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.
0
@warrior though your answer is correct but logic is incorrect!
0

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.



Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true

35,458 questions
42,702 answers
121,328 comments
42,105 users