Un aspecto sorprendente de los AFND es que son equivalentes a los AF; esto quiere decir que todo AFND podrá ser reducido a un AF.

Reducción #

La reducción recae en el hecho que todo AFND tiene un número finito de estados, y podemos imaginarnos que una combinación de estados de un AFND sera equivalente a un estado de un AF. De esta forma cuando en un AFND estamos en una combinación de estados y llega un símbolo, y este nos lleva a otra combinación, en realidad nos estamos moviendo de un estado a otro en el AF a través del mismo símbolo.

Por supuesto, existe un problema exponencial ya que los posibles estados en AF dado un AFND son todas las posibles combinaciones de los estados de este. Tratar de hacer el análisis de dicho número de combinaciones no es práctico. Sin embargo, existe un proceso más directo que no requiere explorar todo este espacio y es a través de codificar los estados del AF con un código posicional de los estados del AFND. Un 1 en el código del AF representa que el estado en el AFND está activo, si hay más unos en el código todos estos estados se encuentran activos, mientas que un 0 representa que el estado correspondiente en el AFND no está activo.

El procedimiento #

Suponiendo un AFND \((Q,\Sigma,q_0,A,\delta)\) el siguiente procedimiento genera la tabla de transición de un AF \((Q',\Sigma,q'_0,A',\delta')\) equivalente:

1. Definir el código para los estados nuestro AF, cada estado \(q\in Q\) define una posición de esa codificación.
2. Agregamos en nuestra tabla una fila para donde estado origen es \(q_0\) cuyo código es la posición del estado inicial activada con un 1 mientras que el restos de las posiciones son cero.
3. Por cada símbolo \(a \in \Sigma \) construir la codificación en la columna correspondiente al símbolo a dónde se activan los estados a los que se llega con dicho símbolo partiendo del estado origen correspondiente a la fila.
4. Por cada codificación nueva que aparezca en las columnas agregar una fila.
5. Si existe un código que no haya sido analizada regresar a 3.

Al final podemos renombrar las codificaciones de los estados con nombres más compactos.

Finalmente, Q será conformado por todos los estados identificados, \(q'_0\) será el estado correspondiente a la codificación creada en el paso 2; A estará conformada por todos los estados cuya codificación tiene activa una posición correspondiente a un estado final del original AFND; y finalmente la tabla de transición representa \(q'_0\) .

Ejemplo #

Supongamos el siguiente orden para nuestros estados del AFND:

Con este orden podemos codificar el estado inicial como:

Con este estado inicial podemos averiguar a dónde llegamos si recibimos cada uno de los símbolos del alfabeto:

En este caso las tres codificaciones resultantes son nuevas, por lo que hay que agregarlas y calcular a dónde podemos llegar si llega uno de los símbolos del alfabeto:

Si hacemos el calculo para estas nuevas filas obtenemos:

Es importante notar que la codificación con sólo ceros, representa que con ese símbolos y el estado en el que se encuentra no se puede llegar ningún estado, es un estado de error.

La tabla final resultante es:

Por supuesto la tabla es incomprensible, pero podemos renombrar los estados de la siguiente forma:

Resultando:

Finalmente, si lo graficamos queda de la siguiente forma: