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} => 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}')=> L_{2}' is not recursively enumerable. So, (B).

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

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.2k
- Engineering Mathematics 4.7k
- Digital Logic 1.9k
- Programming & DS 3.5k
- Algorithms 3k
- Theory of Computation 3.7k
- Compiler Design 1.5k
- Databases 2.8k
- CO & Architecture 2.5k
- Computer Networks 2.9k
- Non GATE 835
- Others 1.2k
- Admissions 263
- Exam Queries 390
- Tier 1 Placement Questions 17
- Job Queries 50
- Projects 6

33,593 questions

40,128 answers

114,021 comments

38,389 users