The Gateway to Computer Science Excellence

+20 votes

Let $L_1$ be a recursive language, and let $L_2$ be a recursively enumerable but not a recursive language. Which one of the following is TRUE?

- $L_1$' is recursive and $L_2$' is recursively enumerable
- $L_1$' is recursive and $L_2$' is not recursively enumerable
- $L_1$' and $L_2$' are recursively enumerable
- $L_1$' is recursively enumerable and $L_2$' is recursive

+28 votes

Best answer

$L_1$ being recursive, we have a TM M for $L_1$ which accepts all words in $L_1$ and rejects all words in $L_1$'. So, this TM also works for $L_1$' by changing the accept and reject states. Thus $L_1$' is recursive.

$L_2$ being recursively enumerable but not recursive means TM for $L_2$ can accept all words in $L_2$ but cannot reject all words not in $L_2 \Rightarrow$ TM for $L_2$' cannot exist (as otherwise TM for $L_2$ could simulate the moves of that TM to reject words in $L_2$') $\Rightarrow L_2$' is not recursively enumerable. So, (**B**).

+2

RE are not closed under Complement then how we can definitely say that complement of RE is not REC enumerable.

+3

RE set is not closed under complement. So, given a r.e. language we cannot say if its complement is r.e. or not.

But any regular language is also r.e. and complement of a regular language is regular and hence r.e. too. Here, for a particular subset of RE set we say complement is closed.

Similarly in the question, we do not have the general RE set but a subset where the languages are not recursive. For those languages complement is guaranteed not to be r.e. -> reason given in answer.

But any regular language is also r.e. and complement of a regular language is regular and hence r.e. too. Here, for a particular subset of RE set we say complement is closed.

Similarly in the question, we do not have the general RE set but a subset where the languages are not recursive. For those languages complement is guaranteed not to be r.e. -> reason given in answer.

+5 votes

as we know **recursive language are closed under complementation** hence L1 is recusrive language so L1' also and it is also recusrive enumerable language

( all options are still open as all satisfy above property )

**recursive**** enumerable language ****are**** not closed under complementation** so it **may be ****recursive**** enumerable language or not **

**case 1: if L' is ****recursive**** enumerable language**

**as we know if L and L' are ****recursive**** enumerable languages then L is recursive language but here in question they mentioned L2 is not ****recusrive**

hence** L2' ****cant**** be ****recursive**** enumerable language**

therfore **L2' accept only case 2 which is L2' is not ****recursive**** enumerable language**

**Ans is B **

- All categories
- General Aptitude 1.9k
- Engineering Mathematics 7.5k
- Digital Logic 2.9k
- Programming and DS 4.9k
- Algorithms 4.4k
- Theory of Computation 6.2k
- Compiler Design 2.1k
- Databases 4.1k
- CO and Architecture 3.4k
- Computer Networks 4.2k
- Non GATE 1.4k
- Others 1.4k
- Admissions 595
- Exam Queries 573
- Tier 1 Placement Questions 23
- Job Queries 72
- Projects 18

50,737 questions

57,366 answers

198,496 comments

105,265 users