2
$\begingroup$

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.

$\endgroup$
1

1 Answer 1

4
$\begingroup$

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}\}$.

$\endgroup$
2
  • $\begingroup$ 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? $\endgroup$
    – Shimon
    Commented Sep 22, 2021 at 8:23
  • 2
    $\begingroup$ 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$. $\endgroup$
    – nir shahar
    Commented Sep 22, 2021 at 8:34

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.