Ver el código de «Transformación de autómata finito no determinista con transición vacía a autómata finito no determinista»

{{Definición|nombre=Transformación de AFND-V a AFND|imagen=AFND-V2AFND.png|concepto=Algoritmo que permite encontrar a partir de un [[AFND-V]] un [[AFND]] estricto equivalente.}}

'''Transformación de autómata finito no determinista con transición vacía a autómata finito no determinista'''. Todo [[autómata finito no determinista con transición vacía]], o sea AFND-V,, puede ser transformado a [[AFND]] utilizando un algoritmo basado en la [[clausura-xi]] que agrupa los estados sin transiciones significativas, dejando solo aquellas que reconocen símbolos del alfabeto del autómata, iterando cada vez así eliminar el indeterminismo por cadenas vacías.

Este algoritmo siempre obtiene un AFND equivalente al que pueden deben aplicarse otras transformaciones para obtener un [[AFD]].

==Algoritmo==
Sea un autómata finito no determinista con transiciones vacías ('''AFND-V''') definido por la 5-tupla ''A=<Q, T, g, F, q<sub>0</sub>>'', donde ''Q'' es el [[conjunto]] de estados, ''T'' el [[alfabeto]] de símbolos terminales, ''g'' la relación de transiciones [[Archivo:Definicion_relacion_transiciones_af.gif|middle]], ''F'' los estados finales, de llegada o aceptación y ''q<sub>0</sub>'' es el estado inicial o de partida, el mismo puede transformarse en un [[autómata finito no determinista]] siguiendo los pasos:
# Se calcula ''A=[[clausura-ε]](q<sub>0</sub>)'', siendo A un conjunto que corresponderá al estado inicial del nuevo autómata.
# Para cada símbolo del alfabeto, se verifican los estados alcanzables a partir de algún estado contenido en ''A'', y se calcula la clausura-ε de dichos estados alcanzables. Si dichas clausuras producen nuevos conjuntos distintos de ''A'', estos serán nuevos estados a los que se accederá a partir de ''A'' y del símbolo correspondiente.
# Se repite lo anterior para cada nuevo conjunto, hasta que no existan transiciones posibles para ningún símbolo del alfabeto.
# Los estados finales serán aquellos que contengan a antiguos estados finales.

==Ejemplo==
Dado el AF ''A=<{Q0,Q1,Q2,Q3,Q4,F1,F2},{a,b},{<Q0,chi,Q1>,<Q1,chi,Q2>,<Q1,chi,Q2>,<Q2,chi,F1>,<Q0,chi,Q3>,<Q3,a,Q4>,<Q4,b,F1>,<Q4,chi,F2>},{F1,F2},Q0>'' y su representación en [[diagrama de estados]]:

[[Archivo:Clausura_Xi_Ejemplo_1.gif|middle]]

Obtener un AFND equivalente.

Las clausuras-xi de cada uno de sus estados serían:

* ''clausura-ε(Q0)={Q0,Q1,Q2,F1,Q3}''.
* ''clausura-ε(Q1)={Q1,Q2,F1}''.
* ''clausura-ε(Q2)={Q2,F1}''.
* ''clausura-ε(F1)={F1}''.
* ''clausura-ε(Q3)={Q3}''.
* ''clausura-ε(Q4)={Q4,F2}''.
* ''clausura-ε(F2)={F2}''.

[[Archivo:Clausura_Xi_Ejemplo_1_Resuelto.gif|middle]]

# Ahora se obtiene el estado inicial ''Q0*=clausura-ε(Q0)={Q0,Q1,Q2,F1,Q3}''.
## ''Q0*'' solo tiene transiciones con el terminal ''a'' partiendo originalmente de ''Q3'' hacia ''Q4'', pero ''Q4*=clausura-ε(Q4))={Q4,F2}''.
# Desde ''Q4*'' se puede tomar la transición no vacía ''<Q4,b,F1>'', con ''F1*=clausura-ε(F1))={F1}''.
# ''F1*'' no tiene transiciones.

Luego, el nuevo autómata finito no determinista sería ''A=<{Q0*,Q4*,F1*}, {a,b}, {<Q0*,a,Q4*>,<Q4*,b,F1*>}, {Q0*,Q4*,F1*}, Q0*>'' con una posible representación en [[diagrama de estados]]:

[[Archivo:AFND-V2AFND_Ejemplo_1_Resuelto.gif|middle]]

==Consecuencias==
La existencia de este método permite la conversión de cualquier AFND-V a un AFND equivalente, es decir la eliminación del indeterminismo por cadena vacía, obtenido comúnmente mediante el [[algoritmo de Thompson]], al obtener un AFND-V a partir de una [[expresión regular]].

Si se deseara obtener a partir del AFND resultante su equivalente determinista, deben realizarse un grupo de [[Transformación de AFND a AFD|transformaciones]] que retiren las transiciones no deterministas del autómata. 

Evidentemente en ninguno de los casos los [[autómata finito|autómatas finitos]] obtenidos deben considerarse los únicos que reconocen el [[lenguaje regular]] en cuestión.

==Vease también==
* [[Transformación de AFND a AFD]].
* [[Lenguaje regular]].
* [[Diagrama de estados]].
* [[Autómata finito no determinista]].
* [[Autómata finito no determinista con transiciones vacías]].
* [[Algoritmo de Thompson]].

==Fuentes==
# Tanembaum, A. Compilers: Principles, Tecniques, and Tools. Tomo 1. ACM Press. 5ta Edición.
# Conferencias de la Asignatura "Compilación 1" del Departamento de Ciencias de la Computación de la [[Universidad de Oriente]]. [[Santiago de Cuba]], [[2000]].
# [http://es.wikipedia.org/wiki/Autómata_finito Autómata finito en Wikipedia]. Consultado el [[25 de noviembre]] de [[2013]].
# Acevedo Martínez, Liesner; Osorio Ramírez, Karel. ''Manual de apoyo a la docencia. Técnicas de Compilación: Manual Práctico para estudiantes de Informática''. Libro electrónico en [[PDF]]. [[UCI]]. [[La Habana]], [[2011]].
</div>
[[Categoría:Matemáticas]][[Categoría:Informática]]