edited by
8,290 views
35 votes
35 votes

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.
edited by

3 Answers

Best answer
39 votes
39 votes

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

edited by
2 votes
2 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.
0 votes
0 votes

Ans is (C)

Detailed Reasoning...

  • If $L$ is REL(Recursively Enumerable Language) then
    • For all strings($w_1$) which belongs to $L$,
      • TM will hold.
    • For some string($w_2$) which does not belongs to $L$,
      • TM will hold
    • For some other strings($w_3$), which does not belongs to $L$,
      • TM will not halt
  • Now for complement of $L$ (For $L’$)
    • If we consider $L’$ is REL
      • $w_1$ should not belongs to $L’$
        • For some strings, we can build halting TM
        • For some strings, we cannot build halting TM
      • $w_2$ should belongs to $L’$
      • $w_3$ should belongs to $L’$
        • For both $w_2$ and $w_3$, we can build halting TM.
    • But if we consider $L’$ as complement of Recursively Enumerable Language $L$, then
      • We have halting TM for $w_1$
        • Which accepts $w_1$
        • We can complement its output to get TM which not accept $w_1$
      • We have halting TM for $w_2$
        • Which do not accepts $w_2$
        • We can complement its output to get TM which accepts $w_2$
      • For $w_3$,
        • If we consider $L’$ as REL then we have halting TM for $w_3$.
        • It means for $L$, we can get halting TM for $w_3$
    • It means, we have halting TM for all type of strings.
    • It means, language L is Recursive. NOT Recursive Enumerable.
Answer:

Related questions

54 votes
54 votes
4 answers
1
go_editor asked Sep 28, 2014
18,706 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 onlyI and III onlyII and III onlyI, II an...
29 votes
29 votes
5 answers
2
go_editor asked Sep 26, 2014
14,786 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\}$...
19 votes
19 votes
4 answers
3
go_editor asked Sep 28, 2014
5,160 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______.