The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
x
+19 votes
1.6k views

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

  1. Neither $L$ nor  $\bar{L}$ is recursively enumerable $(r.e.)$. 
  2. One of $L$ and $\bar{L}$ is r.e. but not recursive; the other is not r.e.
  3. Both $L$ and $\bar{L}$ are r.e. but not recursive.
  4. Both $L$ and $\bar{L}$ are recursive.
asked in Theory of Computation by Veteran (103k points)
edited by | 1.6k views

2 Answers

+22 votes
Best answer

(C) is not possible. If $L$ is re we have a TM that accepts string in $L$. If $L$' is re, we have a TM that accepts strings in $L$'. So, using both these TMs we can make a new TM M which accepts strings in $L$ and rejects strings in $L$' - that is $M$ decides $L$, making $L$ recursive.

answered by Veteran (358k points)
edited by
+4
Can you give an example for option A?
+1
@Shalini If $L$ itself is not RE then $L'$ is also not RE
+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...
0
That seems correct
0
The number of turing machines are countable but total number of languages are uncountable. There are many languages for which turing machines do not exist i.e. they are not recursively enumerable.
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.
answered by Loyal (8.5k points)


Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true

40,855 questions
47,520 answers
145,895 comments
62,278 users