Prueba para la estrella de Kleene y la concatenación

Question

Actualmente estoy aprendiendo lenguajes formales y teoría de autómatas.

Me encontré con una pregunta que no puedo resolver. Necesito probar que para los idiomas $L_1$ y $L_2$ sobre el alfabeto $\Sigma$ : $$ (L_1L_2)^*L_1=L_1(L_2L_1)^* $$

Intenté probarlo con la doble inclusión y decir que $w\in (L_1L_2)^*=>w=xy_1,xy_2...xy_n$ pero no tengo ni idea de cómo continuar esta prueba.

También pensé en ir en la dirección que $(L_1L_2)^=L_1^*L_2^*$ pero no estoy seguro de si esto es cierto y cómo proceder con él.

Agradeceremos cualquier ayuda. Gracias.

Answer 1

Recordemos que $\Sigma^*$ es un monoide bajo la operación de catenación y que para cualquier $L \subseteq \Sigma^*$ , $L^*$ es el submonoide de $\Sigma^*$ generado por $L$ . El hecho de que un conjunto $S \subseteq \Sigma^*$ es un submonoide significa que está cerrado bajo catenación y contiene la cadena vacía $\epsilon$ . El hecho de que $L^*$ es el submonoide generado por $L$ significa que es el submonoide más pequeño que contiene $L$ .

Si $L_1, L_2$ son cualquier idioma, afirmo que

$$M =\{x \in \Sigma^* \mid \forall y \in L_1 . xy \in L_1 (L_2 L_1)^*\}$$

es un submonoide.

Pues considere que dado $x_1, x_2 \in M$ y $y \in L_1$ . Entonces vemos que $x_2 y \in L_1 (L_2 L_1)^*$ . A continuación, escriba $x_2 y = a b$ donde $a \in L_1$ , $b \in (L_2L_1)^*$ . Entonces $x_1 a \in L_1 (L_2 L_1)^*$ Así que escriba $x_1 a = c d$ donde $c \in L_1$ y $d \in (L_2 L_1)^*$ . Entonces tenemos $(x_1 x_2) y = x_1 (x_2 y) = x_1 (ab) = (x_1 a) b = (cd)b = c(db)$ . Ahora $c \in L_1$ y como $d, b \in (L_2 L_1)^*$ y $(L_2 L_1)^*$ es un submonoide, $db \in (L_2 L_1)^*$ . Así, $c(db) \in L_1 (L_2 L_1)^*$ . Así que $m$ se cierra bajo la catenación.

Además, vemos que para todos los $y \in L_1$ tenemos $\epsilon y = y \epsilon$ . Desde $\epsilon \in (L_2 L_1)^*$ tenemos $y \epsilon \in L_1 (L_2 L_1)^*$ . Por lo tanto, $\epsilon \in M$ .

Hemos confirmado que $M$ es un submonoide de $\Sigma^*$ . Ahora, verificamos que $L_1 L_2 \subseteq M$ . Supongamos que tenemos $x \in L_1 L_2$ . Escribe $x = ab$ donde $a \in L_1$ , $b = L_2$ . Entonces, dado $y \in L_1$ tenemos $xy = (ab) y = a (by)$ . Desde $a \in L_1$ y $(by) \in L_2 L_1 \subseteq (L_2 L_1)^*$ tenemos $a (by) \in L_1 (L_2 L_1)^*\}$ . Así, $x \in M$ . Así que $L_1 L_2 \subseteq M$ .

Ahora bien, como $(L_1 L_2)^*$ es el submonoide más pequeño de $\Sigma^*$ que contiene $L_1 L_2$ y como $L_1 L_2 \subseteq M$ y $M$ es un submonoide de $\Sigma^*$ vemos que $(L_1 L_2)^* \subseteq M$ . Por lo tanto, para todos los $x \in (L_1 L_2)^*$ para todos $y \in L_1$ , $xy \in L_1 (L_2 L_1)^*$ . Es decir, $(L_1 L_2)^* L_1 \subseteq L_1 (L_2 L_1)^*$ .

Dejo la otra dirección como ejercicio.

Por cierto, definitivamente no es cierto que $L_1^* L_2^* = (L_1 L_2)^*$ en general. Sólo toma $\Sigma = \{1, 2\}$ y $L_i = \{i\}$ para ver esto.