Autómata finito no determinista con transición vacía

Autómata finito no determinista con transiciones vacías Concepto: Reconocedor de lenguajes regulares que no usa memoria para almacenar los estados de ejecución ni los símbolos del lenguaje, con al menos una transiciones vacía.

Autómata finito no determinista con transiciones vacías, AFND-TV, AFND-V ó . Es el autómata finito que tiene al menos una transición vacía.

Los AFND-TV son definiciones de AFND dentro de los lenguajes regulares que dificultan su implementación mecánica e informática; pero es común obtenerlos a partir de transformaciones a lo interno de los LR (expresiones regulares a AF, gramáticas regulares a AF). Entonces son vitales para el análisis lexicográfico durante el diseño de los lenguajes de programación.

Definición

Sea un autómata finito definido por la 5-tupla A=<Q, T, g, F, q₀>, donde Q es el conjunto de estados, T el alfabeto de símbolos terminales, la relación de transiciones , F son los estados finales o de llegada dentro de Q, q₀ es el estado inicial o de partida; se dice que A es un autómata finito no determinista con transiciones vacías (AFND-TV, AFND-V ó ) si y sólo si existen en g al menos una transición vacía <q_i,,q_j>, donde q_i y q_j son estados cualesquiera de A.

Consecuencias

La definición formal de AFND-V se basa en la consideración de que a menudo según los algoritmos de transformación de expresiones y gramáticas regulares a AF terminan obteniendose autómatas con transiciones múltilples para un mismo símbolo o transiciones vacías.

Independientemente que sean indeseables, sobre todo para la implementación material, fundamentalmente mecánica, de los autómatas finitos; son imprescindibles durante la modelación de analizadores lexicográficos de los elementos gramaticales de los lenguajes de programación, llamados tókenes, como literales numéricos, identificadores, cadenas de texto, operadores, etc.

Transformación de AFND-V a AFND

Artículo principal "Transformación de AFND-V a AFND"

Los AFND-V se pueden transformar a autómatas finitos no deterministas mediante una serie de transformaciones que se basan en la reducción a solo los estados con transiciones significativas determinados por la clausura, siguiendo los pasos:

1. Se calcula A=clausura-v(q₀), que corresponderá al estado inicial del nuevo autómata.
2. Para cada símbolo del alfabeto T, se verifican los estados alcanzables a partir de algún estado contenido en A, y se calcula la clausura-v de dichos estados alcanzables. Si dichas clausuras-v producen nuevos conjuntos distintos de A, es decir conjuntos A_i, estos serán nuevos estados a los que se accederá a partir de A y del símbolo correspondiente.
3. Se repite lo anterior para cada nuevo conjunto A_i obtenido en (2), hasta que no existan transiciones posibles para ningún símbolo del alfabeto.

Vease también

• Lenguaje regular.
• Gramática regular.
• Expresión regular.
• Diagrama de estados.
• Autómata finito.
• Autómata finito determinista.
• Autómata finito no determinista.

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.