next up previous contents
Siguiente: Indeterminismo y determinismo Un nivel arriba: Autómatas no-deterministas Anterior: Representación de transiciones mediante

Monoides de autómas no-deterministas

El monoide de un autómata no-determinista se construye de manera similar a como se hizo en el caso determinista: Dos palabras $\sigma_1,\sigma_2$ son equivalentes, $\sigma_1\equiv_{\mbox{\scriptsize\it AFND}}\sigma_2$, si $M^{\mbox{\scriptsize\it AFND}}(\sigma_1)=M^{\mbox{\scriptsize\it AFND}}(\sigma_2)$, es decir, si ambas definen a la misma relación entre estados. Esta relación[*], además de ser de equivalencia, es congruente con la concatenación. Por tanto, el cociente $S_{\mbox{\scriptsize\it AFND}}=(\mbox{\it Ent\/}/\equiv_{\mbox{\scriptsize\it AFND}})$ es un monoide, dicho del autómata AFND. $S_{\mbox{\scriptsize\it AFND}}$ se construye también siguiendo el algoritmo (3.6).


Ejemplo. Aplicando el algoritmo (3.6) al ejemplo anterior, se obtiene las palabras mostradas en la tabla (3.13).
  
Table 3.13: Cálculo del monoide del autómata no-determinista.
\begin{table}\begin{displaymath}\begin{array}{\vert\vert l\vert l\vert\vert l\ve...
...01 & 001001 & 001 \\ \hline \hline
\end{array}\end{displaymath}
\end{table}

Se ve que exactamente 21 clases de equivalencia conforman el monoide del autómata. En la tabla (3.14) se muestra cada una de las 21 matrices correspondientes.
  
Table 3.14: Matrices correspondientes a los elementos del monoide del autómata no-determinista.
\begin{table}{\tiny
\begin{displaymath}\begin{array}{\vert\vert r\vert r\vert ...
...end{array}\right) \\ \hline\hline
\end{array}\end{displaymath}}
\end{table}

Ahí, observamos que las palabras 11 y 0011 son reconocidas por el autómata (sus entradas $\left(M\right)_{04}$, correspondientes a un arribo al estado final q4 a partir del inicial q0, asumen el valor 1). Por tanto, cualquier palabra equivalente a una de ellas dos también ha de ser reconocida. Se tiene pues que el lenguaje reconocido por el autómata no-determinista es precisamente la unión de las dos clases de equivalencia [11] y [0011]. Por otro lado, el monoide del autómata no-determinista puede ser dotado, como se hizo anteriormente, de una estructura de autómata finito. Si aquí se declara como finales a las clases [11] y [0011] entonces el autómata resultante será uno finito que reconoce al mismo lenguaje que el autómata no-determinista. Esta propiedad de ser equivalente a uno finito no es exclusiva del autómata en este ejemplo según veremos en el lema (3.3.2) más abajo.
next up previous contents
Siguiente: Indeterminismo y determinismo Un nivel arriba: Autómatas no-deterministas Anterior: Representación de transiciones mediante
Guillermo Morales-Luna
2000-06-27