Propiedades de lenguajes regulares

Sean $L_1$ y $L_2$ dos lenguajes regulares.

Unión:

$L=L_1\cup L_2$ es regular, porque podemos construir una expresión regular para $L$, teniendo las expresiones regulares para $L_1$ y $L_2$, más preciso: con $L_1=L(\alpha)$ y $L_2=L(\beta)$ tenemos $L=L((\alpha+\beta))$

Concatención:

$L=L_1.L_2$ es regular, porque podemos construir una expresión regular para $L$, teniendo las expresiones regulares para $L_1$ y $L_2$, más preciso: con $L_1=L(\alpha)$ y $L_2=L(\beta)$ tenemos $L=L(\alpha\beta)$

Clausura:

$L=L_1^*$ es regular, porque podemos construir una expresión regular para $L$, teniendo la expresión regular para $L_1$, más preciso: con $L_1=L(\alpha)$ tenemos $L=L((\alpha)^*)$

Complemento:

$L=\overline{L_1}=\mbox{$\Sigma^*$}-L_1$ es regular, porque podemos construir, dado un AFD completo $M_1$ que acepta $L_1$, un AFD $M$ que acepta $L$ simplemente `invertiendo' sus estados finales, es decir, los estados no finales de $M_1$ serán los estados finales de $M$ y los finales se convierten en los no finales, entonces, si $M_1=(\Sigma,Q,\delta,q_0,F)$ construimos $M=(\Sigma,Q,\delta,q_0,Q-F)$.

Intersección:

$L=L_1\cap L_2$ es regular, porque con las reglas de DeMorgan obtenemos $L=L_1\cup L_2=\overline{\overline{L_1}\cup\overline{L_2}}$. Complemento y unión producen lenguajes regulares, como visto antes. Dicha construcción es bastante laborosa, abajo vemos una construcción directa y simple.

Diferencia:

$L=L_1-L_2$ es regular, porque se puede expresar la diferencia como $L=L_1-L_2=L_1\cap \overline{L_2}=L_1\cap(\mbox{$\Sigma^*$}-L_2)$ y las operaciones usadas mantienen la regularidad.

En vez de usar la lógica booleana, es decir, aplicando las reglas de DeMorgan, se puede construir directamente un autómata que acepta el lenguaje $L=L_1\cap L_2$.

La idea principal es, simular en paralelo en un solo autómata (digamos autómata de producto) las transiciones de los dos autómatas (por ejemplo finitos deterministas y completas) para $L_1$ y $L_2$.

Entonces sean $M_1=(\Sigma_1,Q_1,\delta_1,q_1,F_1)$ y $M_2=(\Sigma_2,Q_2,\delta_2,q_2,F_2)$ los dos AFDs completos que aceptan $L_1$ y $L_2$, es decir, $L_1=L(M_1)$ y $L_2=L(M_2)$.

Construimos el AFD completo $M$ que acepta $L=L_1\cap L_2=L(M)$ como

$$M=(\Sigma,Q,\delta,q_0,F)$$

donde

• asumimos que $\Sigma=\Sigma_1=\Sigma_2$, es decir, usamos solamente los símbolos comunes. Es fácil eliminar en $M_1$ y en $M_2$ todas las dependencias de símbolos superflues antemano en caso que haya.
• $Q=Q_1\times Q_2$, es decir, el producto cartesiano de los estados de $M_1$ y $M_2$.
• $\delta$ es la función de transición con
  
  $$\delta((p,q),\sigma)=(\delta_1(p,\sigma),\delta_2(q,\sigma))$$
  
  
  para $p\in Q_1$, $q\in Q_2$ y $\sigma\in\Sigma$.
• $q_0=(q_1,q_2)$, es decir, la pareja de los dos estados iniciales
• $F=F_1\times F_2$, es decir, todas las parejas donde ambos estados son estados finales de ambos autómatas.

Ejemplo:

Obviamente la construcción funciona igual con autómatas finitos no-deterministas (AFND).

Homomorfismo:

a lo mejor lo incluyo.