# Does $L_1L_2 \notin RE$ imply $L_2L_1 \notin RE$?

Given two languages $$L_1, L_2$$ such that $$L_1L_2\notin RE$$, is it always true that $$L_2L_1 \notin RE$$?

I wasn't able to prove it or find a valid counterexample.

## 1 Answer

Let $$A \subseteq \mathbb{N}$$ be an arbitrary subset containing $$0$$. Define $$L_1 = \{0^n 1 : n \in A\}$$ and $$L_2 = \{0^n : n \in \mathbb{N}\}$$. Then $$A$$ reduces to $$L_1L_2$$, but $$L_2L_1 = \{0^n1 : n \in \mathbb{N}\}$$.

• Thanks a lot for the quick response. but to my understanding your example doesn't give two languages that when concatenated are not recursively enumerable, no? because $$L_1L_2$$ and $$L_2L_1$$ are recursively enumerable, aren't they? Commented Sep 22, 2021 at 8:23
• Note that $L_1$ is defined with respect to $A$, which is totally an arbitrary set. Hence you can choose $A$ such that $L_1$ would not be $RE$, and it will imply that $L_1L_2$ isn't as well (try to prove for yourself). But as you can see, $L_2L_1$ is $RE$. Commented Sep 22, 2021 at 8:34