1
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ 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)? $\endgroup$ – user228113 Aug 13 '16 at 9:12
  • $\begingroup$ Thanks, you caught my actual question. $\endgroup$ – 1 0 Aug 13 '16 at 9:17
  • $\begingroup$ @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. $\endgroup$ – 1 0 Aug 13 '16 at 9:21
4
$\begingroup$

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\}^*$$

Due to Lagrange's four-square theorem.

$\endgroup$
  • $\begingroup$ Thanks for nice explanation. $\endgroup$ – 1 0 Aug 13 '16 at 9:42

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.