[Solved]: Prove that $L_1$ is regular if $L_2$, $L_1L_2$, $L_2L_1$ are regular

ignougroup
Problem Detail: 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?

Asked By : Alejandro Sazo

Answered By : Yuval Filmus

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!
Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/11592  Ask a Question  Download Related Notes/Documents