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.

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.

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 q₄ a partir del inicial q₀, 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.
Siguiente: Indeterminismo y determinismo Un nivel arriba: Autómatas no-deterministas Anterior: Representación de transiciones mediante