Conversión AFD a AFND

QUÉ ES UNA CONVERSION DE UN AFND A UN AFD?

Es el procedimiento para transformar un autómata no determinista aun autómata finito determinista para su mejor comprensión y desarrollo en software, esto por medio de un procedimiento que involucra cuatro sencillos pasos.

PASO 1

Dado un Autómata determinista, identificar sus elementos, en el ejemplo que se mostrará, tiene los siguientes elementos

PASO 2

Agregamos un estado de error al final, que contenga los simbolos del alfabeto, en este ejemplo son 1 y 0, por lo tanto habra una transición del estado de error hacia mismo.

PASO 3

A continuación crearemos una tabla de transiciones la cual nos dará como resultado el AFD. Partiremos del estado inicial {a}, de este estado veremos a que siguiente estado nos lleva con 0 y posteriormente con 1, vemos que con 0 estamos en el estado {a}, pero con 1 estamos en el estado {a.b}.

Ahora que ya tenemos el primer renglon de la tabla de transiciones, vemos que en una transicion hay un estado nuevo, este estado esta en el inciso a, este nuevo estado lo pondremos abajo del estado {a} que ya teniamos y de igual manera vemos que el estado siguiente nos lleva con {0} y con {1}. como se ve que el estado nuevo es {a,b}, entonces veremos la transicion que tiene {a} y {b} con respecto a 0 y posteriormente {a} y {b} con 1.

Este procedimiento se repite hasta llenar la tabla

PASO 4

En este último paso dibujaremos el autómata resultante, se dibujara primeramente el primer estado de la primera columna, (para este ejemplo es el estado{a}), despues de todos los estados de su transicion con 0 y con 1({a} y {b}), despues se dibujara el estado siguiente de la primera columna asi mismo como sus estados de transicion({a,b} dado que {a} ya esta dibujado), si el estado ya esta dibujado no es necesario volver a dibujarlo, solo se hace una transicion, el estado o los estados finales de este nuevo autómata serán todos los que contengan el estado final del autómata original (el estado final es {d} en este ejemplo).