Can you give an example for option A?

The Gateway to Computer Science Excellence

First time here? Checkout the FAQ!

x

+19 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.

+21 votes

Best answer

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.3k
- Engineering Mathematics 5.4k
- Digital Logic 2.1k
- Programming & DS 3.9k
- Algorithms 3.4k
- Theory of Computation 4.2k
- Compiler Design 1.6k
- Databases 3.1k
- CO & Architecture 2.7k
- Computer Networks 3.1k
- Non GATE 1.1k
- Others 1.4k
- Admissions 501
- Exam Queries 447
- Tier 1 Placement Questions 19
- Job Queries 62
- Projects 12

37,941 questions

45,453 answers

131,195 comments

48,210 users