expr regular equivalente

Question

Dada una expresión regular $r_1$ es $(r_1^*)^* = (r_1^*)$ . Sé que es cierto, pero no sé cómo demostrarlo.

¿Sería adecuado fijar $r_1$ a una expresión regular como $(a+b)$ ¿por ejemplo? ¿Demostrando que todos los elementos se encuentran tanto en el lado derecho como en el lado izquierdo? $L((r_1^*)^*)$ es un subconjunto de $L(r_1^*)$ ¿y viceversa?

Traté de usar un FA para mostrar que ambos serían aceptados por el mismo FA pero no creo que sea suficiente para una prueba. por ejemplo esto

FA

Agradecería cualquier tipo de orientación o ayuda.

Answer 1

El siguiente resultado es válido para cualquier lengua $L$ (regular o no): $(L^*)^* = L^*$ . En realidad, un resultado similar es válido para cualquier monoide $M$ . Dado un subconjunto $S$ de $M$ definir $S^*$ como el submonoide generado por $S$ es decir, el submonoide más pequeño de $M$ que contiene $S$ . Equivalentemente $S^*$ es el subconjunto más pequeño $N$ de $M$ que contiene $S$ et $1$ (la identidad de $S$ ) y tal que para todo $x, y \in N$ , $xy \in N$ .

Afirmo que $(S^*)^* = S^*$ . En efecto, puesto que $(S^*)^*$ es un monoide que contiene $S$ contiene el menor monoide que contiene $S$ a saber $S^*$ . Así $S^* \subseteq (S^*)^*$ . Para demostrar la inclusión contraria, dejemos que $N = S^*$ . Entonces $N$ contiene $S^*$ (por definición) y $1$ y para todos $x, y \in N$ , $xy \in N$ (ya que $S^*$ es un monoide). Por lo tanto $N$ contiene el menor monoide con estas propiedades, a saber $(S^*)^*$ . Así $S^* = (S^*)^*$ .

Answer 2

Es evidente que $(r_1*)$ se encuentra en $(r_1*)*$ .

A continuación, demuestre que $(r_1*)(r_1*)$ se encuentra en $(r_1*)$ . (Utilizar doble inducción.)

Por último, demuestre que $(r_1*)*$ se encuentra en $(r_1*)$ . (Utiliza la inducción.)