Operaciones regulares

El conjunto de operaciones {$+$, $\cdot$, $*$}, son llamadas operaciones regulares. Por conveniencia se utiliza el evento 0 como una operación regular nula.
Las operaciones regulares satisfacen los siguientes axiomas:

1. $A+0=A$
2. $A+B=B+A$
3. $(A+B)+C=A+(B+C)$
4. $A\cdot 0=0$
5. $0\cdot A=0$
6. $A\cdot 1=A$
7. $1\cdot A=A$
8. $A(B+C)=AB+AC$
9. $(B+C)A=BA+CA$
10. $(AB)C=A(BC)$
11. $(A+B)^*=(A^*B)^*A^*$
12. $(AB)^*=1+ A(AB)^*B$
13. $(A^*)^*=A^*$
14. $A^*=A^{n*}A^{<n}(n>0)$

Los axiomas del 1-10 son fáciles de analizar, pero explicare los últimos 4. Primero, el axioma $11$ es $(A+B)^*=(A^*B)^*A^*$, si desarrollamos las potencias de esta expresión, obtenemos $1+A+B+AA+AB+BA+BB+\ldots$, que es la suma de todos los productos de $A$'s y $B$'s. Del otro lado de la igualdad tenemos $(A^*B)^*A^*$, la cual podemos expresar como $(A^iB)(A^jB)\ldots(A^mB)A^n$, que es el producto de 0 o más potencias de $A$'s particionadas por la ocurrencia de $B$'s. De manera similar tenemos que

$$(AB)^*=1+AB+ABAB+\ldots=1+A(AB)^*B,$$

con lo que se demuestra el axioma 12. Para $(A^*)^*$ podemos ver sencillamente que $\cup_{j=0}^{\infty}\cup_{i=0}^{\infty} (A^i)^j= \cup_{n=0}^\infty A^n$. El axioma $14$ es muy parecido al $13$, nos dice que podemos escribir cualquier potencia de $A$, digamos $A^t$, como $(A^j)^n.A^k$, donde $0\leq k<n$. Hay que mencionar que es común abreviar $(A^n)^*$ como $A^{n*}$, los exponentes serán tratados como si fueran índices, así que, en adelante podríamos utilizar $A^{n*+\leq n}$ en vez de $(A^n)^*\cdot A^{\leq n}$.
Llamaremos a un evento, regular, sólo si puede ser obtenido de los eventos $0,1$ y las entradas, por medio de la aplicación repetida de las operaciones regulares {$+,\cdot,*$}, es decir, son un función regular de sus entradas. Al hablar acerca de un evento regular estamos hablando al mismo tiempo de un concepto tratado en la sección 2.4, una exresión regular.
Ejemplo: Tomemos a $E=(aa^*ba)^*$, podemos ver que es regular, ya que esta formado por los productos (posiblemente vacíos) de todas las cadenas de la forma $aa^nba\ (n \geq 0)$, este evento es representable, ya que el evento $E$ está constituido por todas las cadenas $w$ de la forma $(aa^*ba)^*$, que logran que la máquina pare en $q_1$, un estado en el cual $o(q_{1w})=1$, esto es, $E(1)=E$. La figura 3 muestra la representación y la tabla 3 muestra las transiciones de estados de la máquina.

Figura 3: Representación de $E=E(1)=(aa^*ba)^*$.

Tabla 3: Tabla de transiciones, para la figura 3.

$t$	$a$	$b$	$o$
$q_1$	$q_2$	$\times$	$1$
$q_2$	$q_2$	$q_3$	0
$q_3$	$q_1$	$\times$	0