automatas


CONVERSIÓN DE AFND EN AFD

A continuación veremos dos diagramas de transición de autómatas finitos no deterministas:













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











Mientras que este reconoce el lenguaje definido por la expresión regular a*. ( a | b ).

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





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







(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ón del AF y disminuye sensiblemente la eficiencia del reconocedor. Por tal motivo es convenientepoder 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 AFD equivalente. Este algoritmo se denomina a menudo, construcción de subconjuntos. En la tabla de transicionesde 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 después de leer cada símbolo de entrada. Esto equivale a decir, que despuésde 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 serexponencial 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 se obtiene 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.

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

 w  * | (S0,w) (S,)


Ejercicio:

A continuación diseñaremos un algoritmo que determine el conjunto de estados accesibles de un AF.


Luego, la idea del algoritmo para convertir a AFD es la misma descritaanteriormente, pero de forma tal que vamos obteniendo para el nuevo autómata solamente los estados accesibles. Por tanto, no se determinan ni se incluyen las transiciones 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 unmomento 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 e-movimientos, ya que en esta decisión no interviene el símbolo de entrada.


En el segundo autómata, 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...