2
$\begingroup$

Prove/Disprove: $L_1, L_2 \in RE-R \implies L_1 \cup L_2 \notin R$

My first intuition is "Yes", since we may look at $M_1, M_2$ which accepts $L_1, L_2$, respectively. Then, WLOG there's $w$ such that $M_1$ doesn't halt for, and so the machine $M$ which runs $M_1, M_2$ in parallel, may not halt.

$\endgroup$
2
  • $\begingroup$ If $w \in L_1$, then $M_1$ must always halt for $w$ $\endgroup$
    – Erbureth
    Commented May 23, 2015 at 13:34
  • $\begingroup$ I've corrected it. was sort of a typo.. $\endgroup$ Commented May 23, 2015 at 13:53

1 Answer 1

7
$\begingroup$

Hint: Let $L$ be any language in $\mathsf{RE} - \mathsf{R}$, and consider $$ L_1 = 0\Sigma^* \cup 1L, \quad L_2 = 1\Sigma^* \cup 0L. $$

$\endgroup$
10
  • $\begingroup$ But $L_1$ mustn't be decidable since it's in $RE-R$. Maybe I'm missing your intention. $\endgroup$ Commented May 23, 2015 at 14:12
  • $\begingroup$ No, I think I misinterpreted your $R$ to mean regular rather than recursive. $\endgroup$ Commented May 23, 2015 at 14:18
  • $\begingroup$ I'm looking at the intersection of $L_1, L_2$ but don't see why $L_1 \cap L_2 \in R$ $\endgroup$ Commented May 23, 2015 at 14:50
  • 2
    $\begingroup$ You can also give a similar example for intersection: $0L$ and $1L$. $\endgroup$ Commented May 23, 2015 at 20:56
  • 1
    $\begingroup$ It's best if you worked it out on your own. $\endgroup$ Commented Jan 26 at 17:49

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.