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?


2 Answers 2


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!

  • 1
    $\begingroup$ I agree. I never looked for counterexamples because the question was "positive" (the author never says prove or refute) Again, nice and simple counterexample. Thanks! $\endgroup$ Apr 27, 2013 at 10:56

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.

  • $\begingroup$ This is a special case of my example with $\Sigma = \{a\}$. $\endgroup$ Apr 29, 2013 at 18:33
  • $\begingroup$ Yes, I will edit my answer to clarify that! $\endgroup$ Apr 29, 2013 at 18:35

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.