Ver el código de «Clausura-Xi»

{{Definición|nombre=Clausura-Xi|imagen=AFND.png|concepto=Operación que devuelve todos los estados accesibles que pueden reconocerse con no más de un símbolo terminal desde uno dado como parámetro.}}

'''Clausura Xi''' ó '''Clausura vacía'''. Operación sobre estados de un [[autómata finito]] (AF) que devuelve todos los estados accesibles desde uno dado como parámetro de la operación [[conjunto|conjuntual]] y a los que se llega con no más de un símbolo terminal del alfabeto del autómata.

Esta operación es básica en el proceso de transformación de [[AFND-V]] a [[AFD]], al permitir la identificación de estados innecesarios para los AFD equivalentes. El proceso de conversión de [[expresión regular]] a [[AF]] genera [[AFND-V|autómatas finitos con transiciones vacías]] que para una mejor implementación deben ser llevados a autómatas finitos deterministas.

==Definición==
Sea un [[autómata finito no determinista con transición vacía]] ''A=<Q,T,g,F,q<sub>0</sub>>'' se define a la '''clasura-xi(q)''', '''clasura-vacía(q)''' ó [[Archivo:Clausura_Chi_Func.gif|middle]] por los siguientes pasos recursivos:
# [[Archivo:Clausura_Xi_Caso_Base.gif|middle]].
# Para todos los pares de estados ''p, r'' del ''A'', si [[Archivo:p_pertenece_Clausura_Xi_de_q.gif|middle]] y [[Archivo:Terna_p_xi_r_pertenece_a_Transiciones.gif|middle]] entonces [[Archivo:r_pertenece_Clausura_Xi_de_q.gif|middle]].

==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]]

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

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

[[Archivo:Clausura_Xi_Ejemplo_1_Resuelto.gif|middle]]

==Consecuencias==
La [[Archivo:Clausura_Chi.gif|middle]] es del tipo [[clausura transitiva]], y se usa en el proceso de eliminación del indeterminismo por transiciones vacías para obtener finalmente un autómata finito determinista.

==Vease también==
* [[Lenguaje regular]].
* [[Expresión regular]].
* [[Autómata finito]].
* [[Autómata finito determinista]].
* [[Autómata finito no determinista con transición vacía]].

==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].
# 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]]