5
$\begingroup$

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?

$\endgroup$
7
$\begingroup$

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!

$\endgroup$
  • $\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$ – Alejandro Sazo Apr 27 '13 at 10:56
2
$\begingroup$

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.

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

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.