Siguiente: Monoides de autómas no-deterministas
Un nivel arriba: Nociones básicas
Anterior: Nociones básicas
Sea
el álgebra booleana de dos elementos, dotada de sus operaciones usuales de conjunción, ``
'' y disyunción, ``
'':
es 1 sólo si ambos x e y son 1;
es 0 sólo si ambos x e y son 0.
Para cada símbolo de entrada
definamos la matriz
tal que para todos
:
Similarmente, para
definamos la matriz
tal que para todos
:
Así pues,
se tiene la relación,
Ahora bien, la colección
de matrices booleanas con índices en Q tiene una estructura de anillo con la operación suma dada por la disyunción entrada a entrada,
y el producto booleano de matrices,
Lema 3.1
Si
![$\sigma=\sigma_1\sigma_2$](img998.gif)
entonces
![$M^{\mbox{\scriptsize\it AFND}}(\sigma)=M^{\mbox{\scriptsize\it AFND}}(\sigma_1)M^{\mbox{\scriptsize\it AFND}}(\sigma_2)$](img999.gif)
.
En particular, si
![$\sigma=e_{i_0}\cdots e_{i_{k-1}}$](img1000.gif)
entonces
![$M^{\mbox{\scriptsize\it AFND}}(\sigma)={\displaystyle\prod_{j=0}^{k-1}M^{\mbox{\scriptsize\it AFND}}(e_{i_j})}$](img1001.gif)
.
Ejemplo. Para el AFND del ejemplo anterior tenemos
Siguiente: Monoides de autómas no-deterministas
Un nivel arriba: Nociones básicas
Anterior: Nociones básicas
Guillermo Morales-Luna
2000-06-27