Prove that $L_1$ is regular if $L_2$, $L_1L_2$, $L_2L_1$ are regular
Pergunta
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?
Solução
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!
Outras dicas
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.