The Gateway to Computer Science Excellence

First time here? Checkout the FAQ!

x

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

+22 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**).

+1

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

0

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.

+2 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.3k
- Engineering Mathematics 5.1k
- Digital Logic 2k
- Programming & DS 3.7k
- Algorithms 3.1k
- Theory of Computation 3.9k
- Compiler Design 1.5k
- Databases 2.9k
- CO & Architecture 2.5k
- Computer Networks 2.9k
- Non GATE 1k
- Others 1.3k
- Admissions 447
- Exam Queries 428
- Tier 1 Placement Questions 17
- Job Queries 55
- Projects 8

35,487 questions

42,746 answers

121,456 comments

42,138 users