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

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