The Gateway to Computer Science Excellence

First time here? Checkout the FAQ!

x

+21 votes

Let $L$ be a language and $\bar{L}$ be its complement. Which one of the following is **NOT **a viable possibility?

- Neither $L$ nor $\bar{L}$ is recursively enumerable $(r.e.)$.
- One of $L$ and $\bar{L}$ is r.e. but not recursive; the other is not r.e.
- Both $L$ and $\bar{L}$ are r.e. but not recursive.
- Both $L$ and $\bar{L}$ are recursive.

0

@Shubham Option A: In figure if your language L lies in outer space(not R E) then its compliment will also lie in outer space(not RE HERE it can idientified using ALAN) so This statement is true.

Option B:: if langugae L is Re but not rec(meaning it is not recursive so **Total turing machine** not possible but RE so **Univarsal turing machine** possible) . L compliment will not be RE (as only recursive lang is closed under compliment).

+25 votes

Best answer

+3

IF L is recursive then L' is also Recursive

IF L is Recursively enumerable then L' is NOT recursively enumerable .

Correct me if wrong...

IF L is Recursively enumerable then L' is NOT recursively enumerable .

Correct me if wrong...

0 votes

A) It is possible if L itself is NOT RE. Then L' will also not be RE. B) Suppose there is a language such that turing machine halts on the input. The given language is RE but not recursive and its complement is NOT RE. C) This is not possible because if we can write enumeration procedure for both languages and it's complement, then the language becomes recursive. D) It is possible because L is closed under complement if it is recursive. Thus, C is the correct choice.

- 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,720 questions

52,818 answers

183,476 comments

68,569 users