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$
3
  • $\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
    Commented Aug 13, 2016 at 9:12
  • $\begingroup$ Thanks, you caught my actual question. $\endgroup$ Commented Aug 13, 2016 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$ Commented Aug 13, 2016 at 9:21

1 Answer 1

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$
1
  • $\begingroup$ Thanks for nice explanation. $\endgroup$ Commented Aug 13, 2016 at 9:42

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .