jueves, 28 de mayo de 2020

Unidad 3-CONVERSIÓN DE AUTÓMATA FINITO NO DETERMINISTA A AUTÓMATA FINITO DETERMINISTA.


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 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,Î)


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

Codigo y Video final de la evidencia del Carrito

El carrito pudimos hacerlo con un arduino para quese mueva , nos faltaron sensores pero es lo que pudimos pagar en el video se muestra que q...