search
Log In
27 votes
3.1k 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.
in Theory of Computation
edited by
3.1k views
0
plz explain a and b in brief ?
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).

 Image result for automata languages graph like regular context free

 

0
It can be a MSQ qus

2 Answers

31 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.


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
4
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
Please explain option A.
1 vote
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.
Answer:

Related questions

41 votes
4 answers
1
6.2k views
Which of the regular expressions given below represent the following DFA? $0^*1(1+00^*1)^* $ $0^*1^*1+11^*0^*1 $ $(0+1)^*1$ I and II only I and III only II and III only I, II and III
asked Sep 28, 2014 in Theory of Computation jothee 6.2k views
18 votes
5 answers
2
3.4k views
Consider the finite automaton in the following figure: What is the set of reachable states for the input string $0011$? $\{q_0,q_1,q_2\}$ $\{q_0,q_1\}$ $\{q_0,q_1,q_2,q_3\}$ $\{q_3\}$
asked Sep 26, 2014 in Theory of Computation jothee 3.4k views
14 votes
4 answers
3
1.8k views
The function $f(x) =x \sin x$ satisfies the following equation: $f''(x) + f(x) +t \cos x = 0$. The value of $t$ is______.
asked Sep 28, 2014 in Calculus jothee 1.8k views
16 votes
3 answers
4
2k views
Identify the correct order in which the following actions take place in an interaction between a web browser and a web server. The web browser requests a webpage using HTTP. The web browser establishes a TCP connection with the web server. The web server sends the requested webpage using HTTP. The web browser resolves the domain name using DNS. 4, 2, 1, 3 1, 2, 3, 4 4, 1, 2, 3 2, 4, 1, 3
asked Sep 26, 2014 in Web Technologies jothee 2k views
...