Siguiente: Monoides de autómas no-deterministas Un nivel arriba: Nociones básicas Anterior: Nociones básicas

Representación de transiciones mediante matrices booleanas

Sea $\mbox{\it Dos\/}=\{0,1\}$ el álgebra booleana de dos elementos, dotada de sus operaciones usuales de conjunción, ``$\land$'' y disyunción, ``$\lor$'': $x \land y$ es 1 sólo si ambos x e y son 1; $x \lor y$ es 0 sólo si ambos x e y son 0. Para cada símbolo de entrada $e\in\mbox{\it Ent\/}$ definamos la matriz $M^{\mbox{\scriptsize\it AFND}}(e)=\left(m_{qp}\right)_{q,p\in Q}\in \mbox{\it Dos\/}^{Q\times Q}$ tal que para todos $q,p\in Q$:

$$m_{qp}=\left\{\begin{array}{ll} 1 &\mbox{\rm si $(q\;e\;p)\i... ... si $(q\;e\;p)\not\in\mbox{\it tran\/}$. } \end{array}\right.$$

Similarmente, para $\sigma \in \mbox{\it Ent\/}^*$ definamos la matriz $M^{\mbox{\scriptsize\it AFND}}(\sigma)=\left(m_{qp}\right)_{q,p\in Q}\in \mbox{\it Dos\/}^{Q\times Q}$ tal que para todos $q,p\in Q$:

$$m_{qp}=\left\{\begin{array}{ll} 1 &\mbox{\rm si $p\in \mbox{... ...p\not\in \mbox{\it tran\/}^*(q,\sigma)$. } \end{array}\right.$$

Así pues, $\forall \sigma\in\mbox{\it Ent\/}^*$ se tiene la relación,

$$\forall q\in Q:\ \mbox{\it tran\/}^*(q,\sigma)=\{p\in Q\vert\left(M^{\mbox{\scriptsize\it AFND}}(\sigma)\right)_{qp}=1\}.$$

Ahora bien, la colección $\mbox{\it Dos\/}^{Q\times Q}$ 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,

$$A+B=C\ \Leftrightarrow\ \forall q,p\in Q:c_{qp}=a_{qp}\lor b_{qp},$$

y el producto booleano de matrices,

$$AB=C\ \Leftrightarrow\ \forall q,p\in Q:c_{qp}=\bigvee_{o\in Q}(a_{qo}\land b_{op}).$$

Lema 3.1   Si $\sigma=\sigma_1\sigma_2$ entonces $M^{\mbox{\scriptsize\it AFND}}(\sigma)=M^{\mbox{\scriptsize\it AFND}}(\sigma_1)M^{\mbox{\scriptsize\it AFND}}(\sigma_2)$. En particular, si $\sigma=e_{i_0}\cdots e_{i_{k-1}}$ entonces $M^{\mbox{\scriptsize\it AFND}}(\sigma)={\displaystyle\prod_{j=0}^{k-1}M^{\mbox{\scriptsize\it AFND}}(e_{i_j})}$.

Ejemplo. Para el AFND del ejemplo anterior tenemos

$$\begin{array}{c@{\ \ \ ,\ \ \ }c} M^{\mbox{\scriptsize\it AF... ... 0 & 1 \\ 0 & 0 & 0 & 0 & 0 \end{array}\right) \end{array}$$

Siguiente: Monoides de autómas no-deterministas Un nivel arriba: Nociones básicas Anterior: Nociones básicas