# Does the fact that $L_1L_2$ and $L_2L_1$ are both regular imply that at least one between $L_1$ and $L_2$ is regular?

Example: True or False : If $L_1$ and $L_2$ are languages such that $L_2$ , $L_1L_2$ , and $L_2L_1$ are all regular, then $L_1$ must be regular?

False : consider $L_1=\{0^{2^i}\mid i>0\}$ and $L_2=\{0\}^*$

I know that regular languages are closed under intersection, union, kleen, complement property. I also read that if $L_1$ and $L_2$ are languages such that $L_2$ , $L_1\cup L_2$ , and $L_2\cap L_1$ are all regular, then $L_1$ need not be regular.

My question:

If $L_1L_2$ and $L_2L_1$ are both regular, must one between $L_1$ and $L_2$ be regular?

• Didn't you already give a counterexample? Or are you asking whether the fact that $L_1L_2$ and $L_2L_1$ are both regular implies that at least one between $L_1$ and $L_2$ is regular (which is a different thing)? – user228113 Aug 13 '16 at 9:12
• Thanks, you caught my actual question. – 1 0 Aug 13 '16 at 9:17
• @G.Sassatelli, You are right, I think this is similar as : I also read that if $L_1$ and $L_2$ are languages such that $L_2$ , $L_1\cup L_2$ , and $L_2\cap L_1$ are all regular, then $L_1$ need not be regular. – 1 0 Aug 13 '16 at 9:21

The answer is "no". Assume as a contradiction that it were true: the claim implies that every language $L$ such that $L^m$ is regular for some $m>0$ is regular itself.
In fact, call $t$ the least positive integer such that $L^t$ is regular. If $t\ge2$, use the claim on $L^{t}=L^{t-1}L=LL^{t-1}$ and derive a contradiction using minimality of $t$ and $t-1>0$.
But now, consider $L=\left\{0^{n^2}\,:\,n\in\Bbb N\right\}$. This is clearly not regular due to pumping lemma. However, $$L^4=\left\{0^{n^2+m^2+s^2+t^2}\,:\,n,m,s,t\in\Bbb N\right\}=\{0\}^*$$