next up previous contents
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$:

\begin{displaymath}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.\end{displaymath}

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$:

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

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

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

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,

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

y el producto booleano de matrices,

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

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{displaymath}\begin{array}{c@{\ \ \ ,\ \ \ }c}
M^{\mbox{\scriptsize\it AF...
... 0 & 1 \\
0 & 0 & 0 & 0 & 0
\end{array}\right)
\end{array}\end{displaymath}





next up previous contents
Siguiente: Monoides de autómas no-deterministas Un nivel arriba: Nociones básicas Anterior: Nociones básicas
Guillermo Morales-Luna
2000-06-27