# Prove that $L_1$ is regular if $L_2$, $L_1L_2$, $L_2L_1$ are regular

Prove that $L_1$ is regular if $L_2$, $L_1L_2$, $L_2L_1$ are regular.

These are the things that I would use to start.

• As $L_1L_2$ is regular, then the homomorphism $h(L_1L_2)$ is regular.
• Let $h(L_1) = L_2$ and $h(L_2) = L_1$, then $h(L_1L_2) = L_2L_1$ is regular (we already know that) or $h(L_2) = \epsilon$ and we get $L_1$
• By reflexing, $L_1L_2 = (L_2L_1)^{R}$, same result.

But i don't know how to, for example, intersect something that gives me $L_1$ in order to preserve closure and finally $L_1$ be regular.

Any help?

Here is a counterexample. Let $L_1$ be any language over some alphabet $\Sigma$ containing the empty string, and let $L_2 = \Sigma^*$. Then $L_2 = L_1L_2 = L_2L_1 = \Sigma^*$ are all regular, but $L_1$ need not be, in fact it could even be uncomputable!
Another counterexample (special case of the first answer) is find just one non regular language in specific and another regular language where $L_1 \subseteq L_2$.
Let $L_1 = \{a^{n^2}, n \geq 0\}$ (it includes $\epsilon$) and $L_2 = \{a^n, n \geq 0\}$. It's concatenation $L_1L_2 = L_2L_1 = L_2$ since the subset property established at the beggining. Then $L_1$ is not necessarily regular.
• This is a special case of my example with $\Sigma = \{a\}$. – Yuval Filmus Apr 29 '13 at 18:33