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.

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.