# $L \in RE/R$ such that $L^R \cup L \in R$

Prove/disprove: $\exists L \in RE/R$ such that $L^R \cup L \in R$

Where in my context, $R$ is the turing decidable, and $RE$ is the recursively enurmable. I tried to find such an $L$ but couldn't. What I know for sure is that I need a language in $RE/R$ such that $L \cup L^R = \Sigma^*$, or am I also wrong?

• Is $L^R$ the set of all reversed words of $L$, or is this something else? – G. Bach Jan 24 '14 at 23:35
• Yes. Reversed words of $L$ – TheNotMe Jan 24 '14 at 23:46
• Do you use $/$ to denote set difference or right quotient? – Raphael Jan 25 '14 at 16:25

First: Such an $L$ exists and $L \cup L^R$ is not necessarily $\Sigma^*$.
Try $L \cup L^R = \{a^nb^n\} \cup \{b^na^n\}$.
For each $n$, $L$ should contain exactly one of the words $a^nb^n$, $b^na^n$. How can you do this so that $L$ is in $RE/R$?
Let $K$ be any set in $RE/R$ and let $L = \{a^nb^n \mid n \in K\} \cup \{b^na^n \mid n \notin K\}$.