¿El hecho de que $L_1L_2$ y $L_2L_1$ son ambos regulares implican que al menos uno entre $L_1$ y $L_2$ ¿es regular?

Question

Ejemplo: Verdadero o Falso : Si $L_1$ y $L_2$ son lenguas tales que $L_2$ , $L_1L_2$ y $L_2L_1$ son todos regulares, entonces $L_1$ debe ser regular?

Falso : considerar $L_1=\{0^{2^i}\mid i>0\}$ y $L_2=\{0\}^*$

---

Sé que los lenguajes regulares son cerrados bajo la propiedad de intersección, unión, kleen, complemento. También he leído que si $L_1$ y $L_2$ son lenguas tales que $L_2$ , $L_1\cup L_2$ y $L_2\cap L_1$ son todos regulares, entonces $L_1$ no tiene por qué ser regular.

Mi pregunta:

Si $L_1L_2$ y $L_2L_1$ son ambos regulares, debe uno entre $L_1$ y $L_2$ ser regular?

Answer 1

La respuesta es "no". Supongamos como contradicción que fuera cierto: la afirmación implica que toda lengua $L$ tal que $L^m$ es regular para algunos $m>0$ es regular en sí mismo.

De hecho, llama $t$ el menor número entero positivo tal que $L^t$ es regular. Si $t\ge2$ Utiliza el reclamo en $L^{t}=L^{t-1}L=LL^{t-1}$ y derivar una contradicción utilizando la minimidad de $t$ y $t-1>0$ .

Pero ahora, considera $L=\left\{0^{n^2}\,:\,n\in\Bbb N\right\}$ . Está claro que esto no es regular debido al lema de bombeo. Sin embargo, $$L^4=\left\{0^{n^2+m^2+s^2+t^2}\,:\,n,m,s,t\in\Bbb N\right\}=\{0\}^*$$

Debido a Teorema de los cuatro cuadrados de Lagrange .