Siguiente: Gráficas de transición Un nivel arriba: Autómatas no-deterministas Anterior: Monoides de autómas no-deterministas

Indeterminismo y determinismo

Diremos que un lenguaje $L\subset\mbox{\it Ent\/}^*$ es regular-N si coincide con el lenguaje reconocido por algún autómata no-determinista. Ya que todo autómata finito es en sí mismo un autómata no-determinista se tiene que todo lenguaje regular es también un lenguaje regular-N. El recíproco también es cierto.

Lema 3.2 (Equivalencia de determinismo e indeterminismo)   Todo lenguaje regular-N es regular. Es decir, para todo autómata no-determinista $\mbox{\it AFND\/}$ existe un autómata finito $\mbox{\it AF\/}$ tal que $L(\mbox{\it AFND\/})=L(\mbox{\it AF\/})$.

En efecto, sea $\mbox{\it AFND\/}=(Q_1,\mbox{\it Ent\/},\mbox{\it tran\/}_1,q_{01},F_1)$ un autómata no-determinista. Podemos presentar dos construcciones de autómatas finitos equivalentes a $\mbox{\it AFND\/}$. Primera construcción. Construyamos el monoide $\mbox{\it S\/}_{\mbox{\scriptsize\it AFND}}$ del autómata no-determinista $\mbox{\it AFND\/}$ y consideremos su estructura de autómata finito: cada uno de sus elementos $[\sigma]$ es un estado, para cada símbolo $e\in\mbox{\it Ent\/}$ definamos la transición $([\sigma], e)\mapsto [\sigma e]$ y definamos como estados finales a las clases de equivalencia $[\sigma]$ tales que $[\sigma]\cap F\not= \emptyset$. Una palabra será reconocida en este último autómata cuando y sólo cuando lo sea por $\mbox{\it AFND\/}$. Segunda construcción. Construyamos el autómata finito $\mbox{\it AF\/}=(Q_2,\mbox{\it Ent\/},\mbox{\it tran\/}_2,q_{02},F_2)$ como sigue:

estados:

Todo subconjunto de estados ``viejos'' será un ``nuevo'' estado, $Q_2={\cal P}(Q_1)=\{Q\vert Q\subset Q_1\}.$

transición:

Todo subconjunto de estados ``viejos'' se transforma en su imagen bajo la función de transición ``vieja'', $\mbox{\it tran\/}_2:Q_2\times\mbox{\it Ent\/} \rightarrow Q_2 , (Q,e) \mapsto \mbox{\it tran\/}_2(Q,e)={\displaystyle \bigcup_{q\in Q}\mbox{\it tran\/}(q,e)}$, es decir, para cada $p\in Q_1$, $p\in\mbox{\it tran\/}_2(Q,e)$ si y sólo si $\exists q\in Q: (q,e,p)\in\mbox{\it tran\/}_1$.

estado inicial:

Hagamos $q_{02}=\{q_{01}\}$, la mónada que consta sólo del estado inicial ``viejo''.

estados finales:

Todo subconjunto de estados ``viejos'' que contenga alguno final de ésos será un nuevo estado final: $Q'\in F_2\; \Leftrightarrow\; Q'\cap F_1\not=\emptyset.$

Observamos que rige cada una de las siguientes equivalencias para cualquier palabra $\sigma\in\mbox{\it Ent\/}$:

$$\begin{eqnarray*}\sigma\in L(\mbox{\it AFND\/}) &\Leftrightarrow& \mbox{\it tran... ...a)\in F_2 \\ &\Leftrightarrow& \sigma\in L(\mbox{\it AF\/}) \end{eqnarray*}$$

así pues, $\mbox{\it AFND\/}$ y $\mbox{\it AF\/}$ son equivalentes. Observemos también aquí que el nuevo conjunto de estados ha de tener 2ⁿ elementos, donde n es el número de estados ``viejos''. Esto hace crecer mucho el tamaño del autómata finito equivalente construído de esta forma. Bien que en algunos casos tal cota superior al número de estados nuevos puede alcanzarse, en muchos otros casos la parte accesible del autómata construído incluirá sólo una cantidad mucho menor de estados. Por tanto, en la práctica es muy conveniente construir tan solo la parte accesible del autómata $\mbox{\it AF\/}$ siguiendo la estrategia del algoritmo (3.5) de cálculo de estados accesibles.


Ejemplo. Consideremos el mismo ejemplo tratado en esta sección. Cada subconjunto Q del conjunto de estados $Q_1=\{q_0,q_1,q_2,q_3,q_4\}$ puede ser codificado por una cadena de 5 caracteres $c_Q=c_{0Q}c_{1Q}c_{2Q}c_{3Q}c_{4Q}\in\{0,1\}^5$ de manera evidente,

$$\forall i\leq 5: c_{iQ}=\left\{\begin{array}{ll} 1 &\mbox{\r... ..., } \\ 0 &\mbox{\rm si $q_i\not\in Q$. } \end{array}\right.$$

y cada una de tales cadenas puede ser vista como la representación binaria de un número entero entre 0 y 31. Nombremos pues con números de 0 a 31 a los elementos del conjunto Q₂ de nuevos estados. Así por ejemplo ``7'' que en binario es 00111 representa al conjunto $\{q_2,q_3,q_4\}$ y ``16'', 16=(10000)₂, es el nuevo estado inicial $q_{02}=\{q_{0}\}$. Los nuevos estados finales son todos aquellos que contegan a q₄, es decir, que tengan el último bit ``prendido''. Los nuevos estados finales son entonces todos los números impares. Con ayuda de la tabla (3.14), se ve que la función de transición del nuevo autómata es la mostrada en la tabla (3.15).

  

Table 3.15: Transición en el autómata finito equivalente al no-determinista.

Observamos en este ejemplo que hay muchos estados inaccesibles tan sólo por el hecho de que la imagen de la función de transición no incluye a todos los estados. Con el estímulo 0 sólo se puede arribar a los estados 0, 4, 8, 12, 16, 20, 24 y 28. Con el estímulo 1 sólo se puede arribar a los estados 0, 2, 13 y 15. Si se aplica el algoritmo (3.5) se obtiene el autómata de 8 estados cuya tabla de transición es la siguiente:

$$\begin{array}{\vert\vert r\vert rr\vert\vert r\vert rr\vert\v... ...&16 & 0 & 13 &28 & 2 & 28 &28 & 2 \\ \hline \hline \end{array}$$

en el que ``16'' es el estado inicial y ``13'' es el único estado final.
Siguiente: Gráficas de transición Un nivel arriba: Autómatas no-deterministas Anterior: Monoides de autómas no-deterministas