Afd Afnd

TRANSFORMACIONES EN AUTÓMATAS FINITOS

Conversión de AFND en AFD
Dados dos autómatas finitos no deterministas cuyos diagramas de transición son los siguientes:
[pic]






Este autómata reconoce el lenguaje de las cadenas sobre {1,2,3} que terminan en un símbolo que haya aparecido previamente.




y
[pic]




Reconoce el lenguaje definido por laexpresión regular a*.(a|b)






En ambos casos podemos ver que existen estados para los cuales hay más de una transición ante un mismo símbolo de entrada:
[pic]




((S0,1) = { S0,S1}




[pic]


((0,() = { 1,3}






Desde el punto de vista de programación, esta situación es importante que no suceda, debido a que se dificulta la representacióndel 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 continuación un algoritmo que construye, a partir de un AFND, un AFDequivalente. Este algoritmo se denomina a menudo, construcción 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 elAFND puede encontrarse después de leer cada símbolo de entrada. Esto equivale a decir, que después de leer los símbolos a1a2...an, el AFD se encuentra en un estado que representa el subconjunto de todos los estados que son alcanzables partiendo del estado inicial del AFND a través de algún camino a1a2...an.
Así por ejemplo, los estados del AFD del 1er autómata serían:


{ { S0}, {S1}, { S2}, { S3}, { Sf}, { S0,S1}, { S0,S2},...} = P(S)


El número de estados en el AFD puede ser exponencial con respecto el número de estados del AFND. Si el AFND tiene n estados, el AFD puede llegar a tener 2n estados, pero en la práctica este caso crítico ocurre raramente. Las transiciones para cada uno de los nuevos estados se determinan formando el conjunto de estados que seobtiene al aplicar la función de transición 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 construcción del AFD no es conveniente realizarla de esta manera, puesto que de los 2 n posibles estados del nuevo autómata existen algunos(probablemente muchos) que no cumplen ninguna función, ya que son inaccesibles en el autómata.


Definición: Un estado es inaccesible si no existe alguna cadena para la cual, el autómata pueda llegar a él partiendo de la configuración inicial, realizando un número finito de transiciones.


Definiremos formalmente los estados accesibles:


El estado S es accesible, si:( w ( (* | (S0,w) [pic] (S,()


Ejercicio propuesto:


Diseñar 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 autómata solamente los estados accesibles. Por tanto, no se determinan ni se incluyen lastransiciones de los estados inaccesibles.
El algoritmo debe tener en cuenta los e-movimientos, que representan transiciones a estados sin tener en cuenta el símbolo actual. Los e-movimientos incorporan cierta complejidad al algoritmo, ya que en un momento dado, si el autómata está en un estado que posee e-movimientos, podrá también estar en cualquiera de los estados a los cuales se pasa por esos...