Clausura-Xi

Clausura-Xi 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 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 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₀> se define a la clasura-xi(q), clasura-vacía(q) ó por los siguientes pasos recursivos:

1. .
2. Para todos los pares de estados p, r del A, si y entonces .

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:

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}.

Consecuencias

La 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

1. Tanembaum, A. Compilers: Principles, Tecniques, and Tools. Tomo 1. ACM Press. 5ta Edición.
2. Conferencias de la Asignatura "Compilación 1" del Departamento de Ciencias de la Computación de la Universidad de Oriente. Santiago de Cuba, 2000.
3. Autómata finito en Wikipedia.
4. 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.