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

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

+2 votes

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

Ans D) Recursive , is correct option.

+3

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

+1 vote

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

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

0 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

- All categories
- General Aptitude 1.6k
- Engineering Mathematics 7.3k
- Digital Logic 2.7k
- Programming & DS 4.9k
- Algorithms 4.2k
- Theory of Computation 5.4k
- Compiler Design 2.1k
- Databases 4k
- CO & Architecture 3.5k
- Computer Networks 4.2k
- Non GATE 1.4k
- Others 1.5k
- Admissions 570
- Exam Queries 566
- Tier 1 Placement Questions 23
- Job Queries 70
- Projects 18

48,691 questions

52,776 answers

183,437 comments

68,391 users