The Gateway to Computer Science Excellence

First time here? Checkout the FAQ!

x

+17 votes

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

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

+25 votes

Best answer

+1 vote

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

Ans D) Recursive , is correct option.

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

*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.2k
- Engineering Mathematics 4.8k
- Digital Logic 2k
- Programming & DS 3.5k
- Algorithms 3k
- Theory of Computation 3.8k
- Compiler Design 1.5k
- Databases 2.8k
- CO & Architecture 2.5k
- Computer Networks 2.9k
- Non GATE 940
- Others 1.2k
- Admissions 320
- Exam Queries 409
- Tier 1 Placement Questions 17
- Job Queries 52
- Projects 8

34,170 questions

40,845 answers

115,883 comments

39,703 users