|
(Etiqueta: Artículo sin Fuentes o Bibliografía o Referencias o Enlaces externos) |
| Línea 1: |
Línea 1: |
| − | {{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.}}
| + | #REDIRECCIÓN [[Clausura_(Grafos)]] |
| − | <div align="justify">
| + | [[Categoría:Redirecciones]] |
| − | '''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|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]]
| |
