Problem Detail: For $L_1, L_2 $ and $L_1 in RE $ and $ L_1notin R$ and $L_2 in RE $ and $ L_2notin R$ I was asked to prove/disprove if the following can occur:
- $L_1 cap L_2 in R$
- $L_1 cup L_2 in R$
- $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!
Asked By : Mark
Answered By : David Richerby
- Correct. We can have $L_1cap L_2=emptysetin 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.
- 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_2cuptext{something else}$ in a way that gives $L_1cup L_2=K_1cup K_2$.
- Correct. We know that $L_1in RE$. Use $L_1cap L_2in R$ and $L_1cup L_2in 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_1in R$, contradicting the requirement that $L_1in REsetminus R$.
Best Answer from StackOverflow
Question Source : http://cs.stackexchange.com/questions/23826
