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

The Gateway to Computer Science Excellence

First time here? Checkout the FAQ!

x

+16 votes

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

- regular
- context-free
- context-sensitive
- recursive

+27 votes

Best answer

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

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

+1 vote

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

Ans D) Recursive , is correct option.

+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.

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

@ 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.

- All categories
- General Aptitude 1.4k
- Engineering Mathematics 5.7k
- Digital Logic 2.2k
- Programming & DS 4.1k
- Algorithms 3.6k
- Theory of Computation 4.5k
- Compiler Design 1.7k
- Databases 3.2k
- CO & Architecture 2.8k
- Computer Networks 3.2k
- Non GATE 1.1k
- Others 1.5k
- Admissions 503
- Exam Queries 474
- Tier 1 Placement Questions 22
- Job Queries 61
- Projects 13

39,776 questions

46,779 answers

140,745 comments

58,654 users