Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

For $L_1, L_2 $ and $L_1 \in RE $ and $ L_1\notin R$ and $L_2 \in RE $ and $ L_2\notin R$

I was asked to prove/disprove if the following can occur:

  1. $L_1 \cap L_2 \in R$
  2. $L_1 \cup L_2 \in R$
  3. $L_1 \cap L_2 \in R$ and $L_1 \cup L_2 \in R$

For 1., I think any two disjoint langauges will suffice (because the empty set is decideable).

For 2., I think something along the lines of a language and its complement but I'm struggling to think of an example.

For 3,. it seems impossible but I have no idea how to prove it.

Any help/further insight would be welcomed!

share|cite|improve this question
Note that for 1, it's not enough to show that some particular $L_1$ and $L_2$ have an intersection in $R$. I'm guessing they want you to show it's true for all RE languages i.e. that RE is closed under intersection. If you're disproving closure, one counter-example is enough though. – jmite Apr 15 '14 at 20:37
@jmite It's absolutely enough to show that some particular $L_1$, $L_2$ have an intersection in $R$! The question asks, is it possible? So an answer to any of the parts would be either a particular $L_1$ and $L_2$ with the required property, a proof that such a pair exists, or a proof that no $L_1$, $L_2$ have that property. – David Richerby Apr 15 '14 at 20:41
For your second point, recall that if a language and its complement both are recursively enumerable, then they are recursive as well. – Pål GD Apr 15 '14 at 21:01
up vote 4 down vote accepted
  1. Correct. We can have $L_1\cap L_2=\emptyset\in R$. A good answer would give an example of such a pair $L_1$, $L_2$ so you should figure that out on your own.

  2. Correct but for the wrong reason. If $L_1$ and its complement are both $RE$, then both are recursive and the question says that neither is recursive. You should prove this yourself, as you'll need it for the next part.

    • Hint for this proof: show how to use machines that accept $L_1$ and $\overline{L_1}$ to give a machine that decides $L_1$.)
    • Hint for the question: take a recursives language $K_1$ and $K_2$ and set $L_1=K_1 \cup \text{something}$ and $L_2=K_2\cup\text{something else}$ in a way that gives $L_1\cup L_2=K_1\cup K_2$.
  3. Correct. We know that $L_1\in RE$. Use $L_1\cap L_2\in R$ and $L_1\cup L_2\in R$ to show that $\overline{L_1}\in RE$. By the extra proof I suggested you do in the previous part, that means that $L_1\in R$, contradicting the requirement that $L_1\in RE\setminus R$.

share|cite|improve this answer

Hint for 2: Consider $L_1 = \{ 0 w : w \in L \} + \{ 1 w : w \in \{0,1\}^* \}$ and let $L_2$ be a complementary language.

Hint for 3: $L_2 \setminus (L_1 \cap L_2) = \overline{L_1} \cap L_2$ and $\overline{L_1 \cup L_2} = \overline{L_1} \cap \overline{L_2}$.

share|cite|improve this answer
What is the explanation for $L_2 \setminus (L_1 \cap L_2) = \overline{L_1} \cap L_2 \in R$? – Elimination May 25 '15 at 12:41
@Elimination It's in RE rather than in R. You're missing the point. Keep thinking. – Yuval Filmus May 25 '15 at 13:42
I actually figured it out and thought I removed my comment. Thank you for responding though :) – Elimination May 25 '15 at 14:09

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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