CONVERSIÓN
DE AFND EN AFD
A continuación veremos
dos diagramas de transición de autómatas finitos no deterministas:
Mientras que este reconoce
el lenguaje definido por la expresió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:
d(S0,1)
= { S0,S1}
d(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 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 AFD equivalente. 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
el AFND 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 se obtiene
al aplicar la función de transición original a cada uno de los estados del
conjunto.
Así por ejemplo:
d'({
S0,S1},1) = d(S0,1)
È d(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 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.
El estado S es accesible,
si:
$ w Î S* |
(S0,w) 
(S,Î)
(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 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 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 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 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 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 partiendo de él por
e-movimientos. Denominaremos e-clausura(S) a la función que calcula todos los
estados a los cuales se puede llegar por Î-movimientos partiendo de
S. Esta función podemos extenderla para calcular la e-clausura de un conjunto
de estados como la unión de las e-clausuras de cada uno de los estados del
conjunto.
Esto es, e-clausura ({
a,b} ) = e-clausura(a) È
e-clausura(b).
Así,
e-clausura (0)
= { 0,1,3,4,6}
e-clausura (0,5)
= { 0,1,3,4,6,5,8}
Algoritmo Obtención de e-clausura(T),
donde T es un conjunto de estados.
colocar
todos los estados de T en una pila
inicializar
e-clausura(T) con T
mientras
la pila no esté vacía hacer
 |
sacar
U de la pila
para
cada estado V tal que , hacer
si
U Ï
e-clausura(T)
añadir
V a e-clausura(T)
colocar
V en la pila
Necesitaremos también una
función que para un conjunto de estados T y un símbolo a, calcule los estados a
los cuales se puede llegar a través de a, partiendo de los estados de T.
Denominaremos a esta función mover(T,a).
El algoritmo para obtener
el AFD construye el autómata simulando todos los posibles movimientos del AFND
ante cualquier cadena de entrada. A través de esta simulación se van obteniendo
los estados del AFD.
Algoritmo:
Construcción de un AFD a partir de un AFND
Entrada: Un AFND N = (S,å,d,S0,F)
Salida: Un AFD N' = (S',å',d,S'0,F'), tal
que L(N) = L(N')
1. S'0 = e-clausura( {S0} )
2. S' = {S'0} e indicar en S' que S0'
está no marcado
3. mientras exista un estado T no marcado en S' hacer
marcar
T
para
cada símbolo a Î
å
hacer
A = mover(T,a)
U
= e-clausura(A)
si
U ÎS'
entonces
añadir
U a S' como un estado no marcado |
d'(T,a) = U
4. F' son todos los estados T de S' que
contengan algún estado de F, o sea, TÇF=0
Notemos que si el
autómata no tiene e-movimientos, entonces S0' = { S0} y
alobtener las transiciones del estado T ante el símbolo a, solo es necesario
calcular mover(T,a).
Si el AFND no tiene
e-movimientos, entonces e-clausura(T) = T.
Ejemplo: Apliquemos el
algoritmo al segundo autómata de la conferencia
e-clausura(0)
= { 0,1,3,4,6} = A
mover(A,a)
= { 2,5}
d'(A,a) = e-clausura({
2,5} ) = { 2,5,1,3,4,6,8} = B
mover(A,b)
= { 7}
d'(A,b) = e-clausura( { 7}
) = { 7,8} = C
mover(B,a) = { 2,5}
d'(B,a) = e-clausura( {
2,5} ) = B
mover(B,b) = { 7}
d'(B,b) = e-clausura( { 7}
) = C
mover(C,a) = { Æ}
d'(C,a) = e-clausura( { Æ} ) = { Æ} = D
mover(C,b)
= { Æ}
d'(C,b) = e-clausura( { Æ} ) = { Æ} = D
mover(D,a)
= { Æ}
d'(D,a) = e-clausura( { Æ} ) = D
mover(D,b)
= { Æ}
d'(D,b) = e-clausura( { Æ} ) = D
|
|
d'
|
a
|
b
|
|
{ 0,1,3,4,6}
|
A
|
B
|
C
|
|
{ 2,5,1,3,4,6,8}
|
B
|
B
|
C
|
|
{ 7,8}
|
C
|
D
|
D
|
|
{ Æ}
|
D
|
D
|
D
|
Los estados finales del
nuevo autómata serían: F = { B,C }
Reconoce a*.(a|b)
No hay comentarios:
Publicar un comentario