algoritmo de transformacion de AFD a AFND

CONVERSIN DE AFND EN AFD A continuacin veremos dos diagramas de transicin de autmatas finitos no deterministas Este autmata reconoce el lenguaje de las cadenas sobre 1, 2, 3 que terminan en un smbolo que haya aparecido previamente. Mientras que este reconoce el lenguaje definido por la expresin regular a. ( a b ). En ambos casos podemos ver que existen estados para los cuales hay ms de unatransicin ante un mismo smbolo de entrada ((S0,1) S0,S1 ((0,() 1,3 Desde el punto de vista de programacin, esta situacin es importante que no suceda, debido a que se dificulta la representacin del AF y disminuye sensiblemente la eficiencia del reconocedor. Por tal motivo es conveniente poder transformar un AFND en un AFD equivalente, o sea, que reconozca el mismo lenguaje. Por otra parte,los AF que se obtienen a partir de expresiones regulares son no deterministas con (-transiciones. Presentaremos a continuacin un algoritmo que construye, a partir de un AFND, un AFD equivalente. Este algoritmo se denomina a menudo, construccin de subconjuntos. En la tabla de transiciones de un AFND, cada entrada es un conjunto de estados mientras que en la de un AFD, cada entrada es un nico estado.La idea general de este algoritmo es asociar a cada conjunto de estados del AFND, un nuevo estado en el AFD. Cada estado en el AFD representa todos los posibles estados en los cuales el AFND puede encontrarse despus de leer cada smbolo de entrada. Esto equivale a decir, que despus de leer los smbolos a1a2...an, el AFD se encuentra en un estado que representa el subconjunto de todos los estados queson alcanzables partiendo del estado inicial del AFND a travs de algn camino a1a2...an. As por ejemplo, los estados del AFD del 1er autmata seran S0, S1, S2, S3, Sf, S0,S1, S0,S2,... P(S) El nmero de estados en el AFD puede ser exponencial con respecto el nmero de estados del AFND. Si el AFND tiene n estados, el AFD puede llegar a tener 2n estados, pero en la prctica este caso crticoocurre raramente. Las transiciones para cada uno de los nuevos estados se determinan formando el conjunto de estados que se obtiene al aplicar la funcin de transicin original a cada uno de los estados del conjunto. As por ejemplo (( S0,S1,1) ((S0,1) ( ((S1,1) S0,S1,Sf . Este, por supuesto, es uno de los estados del AFD. Sin embargo, la construccin del AFD no es conveniente realizarla de estamanera, puesto que de los 2 n posibles estados del nuevo autmata existen algunos (probablemente muchos) que no cumplen ninguna funcin, ya que son inaccesibles en el autmata. Un estado es inaccesible Si no existe alguna cadena para la cual, el autmata pueda llegar a l partiendo de la configuracin inicial, realizando un nmero finito de transiciones. El estado S es accesible, si ( w ( ( (S0,w) (S,()Ejercicio A continuacin disearemos un algoritmo que determine el conjunto de estados accesibles de un AF. Luego, la idea del algoritmo para convertir a AFD es la misma descrita anteriormente, pero de forma tal que vamos obteniendo para el nuevo autmata solamente los estados accesibles. Por tanto, no se determinan ni se incluyen las transiciones de los estados inaccesibles. El algoritmo debe tener encuenta los e-movimientos, que representan transiciones a estados sin tener en cuenta el smbolo actual. Los e-movimientos incorporan cierta complejidad al algoritmo, ya que en un momento dado, si el autmata est en un estado que posee e-movimientos, podr tambin estar en cualquiera de los estados a los cuales se pasa por esos e-movimientos, ya que en esta decisin no interviene el smbolo de entrada.En el segundo autmata, por ejemplo, al comenzar el reconocimiento de una cadena, realmente se puede estar en cualquiera de los estados 0, 1, 3, 4 y 6, ya que el estado inicial 0 posee dos e-movimientos a los estados 1 y 3, y el estado 3 a su vez posee dos e-movimientos a 4 y a 6. Por lo tanto, se hace necesario conocer para cada estado, el conjunto de estados a los cuales se puede llegar...