0
$\begingroup$

Proove or Disproove $ \exists L_1 , L_2 \in RE \setminus R $ such that $ L_1 \cup L_2 \in R $ and $ L_1 \cap L_2 \in R $

I tried to use the languages

enter image description here

the union is $ \sigma^* $ and the intersection is empty language but I am really not sure if that really answer the question

$\endgroup$
3
  • 1
    $\begingroup$ Try to show that the complement of $L_1$ is r.e. by combining the other languages mentioned. $\endgroup$ Commented Jan 26 at 16:08
  • $\begingroup$ hi i am really new to this type of question $\endgroup$
    – maya cohen
    Commented Jan 26 at 16:22
  • 2
    $\begingroup$ The second part of the definitions of $L_1$ and $L_2$ doesn't even make sense. Ignoring this, the neither $L_1 \cap L_2$ nor $L_1 \cup L_2$ are going to be decidable, and neither $L_1$ nor $L_2$ is going to be computably enumerable. $\endgroup$
    – Arno
    Commented Jan 26 at 18:01

1 Answer 1

2
$\begingroup$

Let us assume that $L_1$ and $L_2$ are both computably enumerable, and that $L_1 \cap L_2$ and $L_1 \cup L_2$ are decidable. I claim that $L_1$ is decidable, too.

Given some $w \in \Sigma^*$, I want to determine whether $w \in L_1?$. I proceed as follows:

  1. First, I test whether $w \in L_1 \cup L_2$. If not, I can stop and answer no.
  2. Second, I test whether $w \in L_1 \cap L_2$. If yes, I can stop and answer yes.
  3. Otherwise, I know that $w$ belongs to exactly one of $L_1$ and $L_2$. I run the semi-decision procedures I have for these in parallel, until one of them stops (which has to happen). If I learn that $w \in L_1$, I answer yes. If I learn that $w \in L_2$, I answer no.
$\endgroup$
12
  • $\begingroup$ hi @Arno i am sorry i fixed my question $\endgroup$
    – maya cohen
    Commented Jan 26 at 19:00
  • 1
    $\begingroup$ @mayacohen The answer is still fine as it shows that the claim is wrong. $\endgroup$ Commented Jan 26 at 19:33
  • $\begingroup$ i dont understand the answer but I can accept it, if there is a possibility to make it so that I can understand it I would really appreciate it $\endgroup$
    – maya cohen
    Commented Jan 26 at 19:58
  • 2
    $\begingroup$ @mayacohen If you are completely lost when reading my answer, you aren't ready for this kind of question yet, and you should go back to the basics. If there is one concrete step you don't follow, be specific. $\endgroup$
    – Arno
    Commented Jan 26 at 23:13
  • 2
    $\begingroup$ @mayacohen Because that's not the negation of the claim. $\endgroup$
    – Arno
    Commented Jan 27 at 8:59

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.