Análisis léxico: Autómatas de estado finito
Introducción
¡Hola!
Qué gusto poder encontrarte en esta nueva sesión, espero que sigas descubriendo este curso y lo sigas viendo fascinante. Por lo tanto, te doy la más cordial bienvenida a esta clase digital 6.
En esta sesión aprenderemos sobre la teoría y antecedentes de los autómatas finitos.
Los autómatas finitos son capaces de reconocer lenguajes regulares. De hecho, las expresiones regulares se pueden implementar usando autómatas finitos.
En teoría, para cada expresión regular, existe un autómata finito no determinístico y un autómata finito determinístico que la pueden reconocer.
La teoría de autómatas (o teoría de la computación) es una rama teórica de las ciencias computacionales que estudia máquinas abstractas y autómatas, así como los problemas computacionales que se pueden resolver con ellos. Por lo tanto, la teoría de los autómatas finitos es muy importante para los ingenieros de ciencias computacionales.
El conocimiento sobre la teoría de los autómatas finitos y su relación con las expresiones regulares permite comprender mejor el diseño e implementación de analizadores léxicos.
En conclusión, la teoría de los autómatas de estado finito tiene relación con la teoría de los lenguajes formales que vimos en la sesión anterior.
Otra razón para conocer sobre la teoría de los autómatas de estado finito es que las herramientas Lex y flex generan autómatas finitos no determinísticos.
Existen dos tipos de autómatas finitos: Autómatas finitos determinísticos y Autómatas finitos no determinísticos. Ambos tipos de autómatas son capaces de reconocer los mismos lenguajes regulares.
Sin más preámbulo, ¡comencemos!
¡Éxito!
Desarrollo del tema
Teoría de autómatas:
La teoría de autómatas (o teoría de la computación) es una rama teórica de las ciencias computacionales que estudia máquinas abstractas y autómatas, así como los problemas computacionales que se pueden resolver con ellos. La palabra autómata proviene de la palabra griega αὐτόματος, que significa «auto actuación, voluntad propia, auto movimiento». Un autómata (Autómatas en plural) es un dispositivo informático autopropulsado abstracto que sigue automáticamente una secuencia predeterminada de operaciones.
Los autómatas finitos sólo son capaces de reconocer lenguajes regulares. De hecho, las expresiones regulares fueron implementadas por primera vez por Thompson usando autómatas finitos.
El análisis léxico está basado en expresiones regulares para el reconocimiento de las unidades del lenguaje o tokens.
Reconocimiento de Tokens:
- El objetivo del reconocimiento de tokens es construir un analizador léxico que produzca tokens y los valores de sus atributos asociados
Existen dos métodos para implementar el reconocimiento de tokens: manual o basado en herramientas.
- El método manual consiste en construir o diseñar y simular autómatas finitos (AF/AEF: Autómata (de Estado) Finito).
- El método basado en herramientas consiste en usar expresiones regulares para que el generador de código construya los autómatas finitos para el analizador léxico.
Autómata (de Estado) Finito:
Un autómata finito se puede especificar por medio de:
- Un conjunto de estados:
- S
- Un conjunto de símbolos de entrada:
- Una función de transición: s,a=s’
- Un estado inicial: s0
- Un conjunto de estados finales: F
Un autómata finito se puede representar de forma gráfica por medio de un diagrama de transición de estados.
Existen dos tipos de autómatas finitos:
- Autómatas finitos determinísticos (AFD)
Los cuales se caracterizan por tener a lo más una transición para cada símbolo de entrada.
- Autómatas finitos no determinísticos (AFN)
Los cuales pueden tener más de una transición para algún símbolo de entrada.
Autómata Finito Determinístico:
- Un AFD es un caso especial de AFN en el cual:
Ningún estado tiene transición ε
Para cada estado s y símbolo de entrada a hay a lo más una etiqueta a que sale del estado s
Autómata Finito No Determinístico:
- Un AFN se puede representar por medio de:
- S: un conjunto finito de estados
- : un conjunto finito de símbolos de entrada
- : una función de transición que mapea pares (estado, símbolo) a estados
- s0: un estado llamado estado inicial
- F: un conjunto de estados llamado estados finales
- Un AFN acepta una cadena de entrada s si y sólo si hay alguna ruta en el diagrama de transición desde el estado inicial hasta algún estado final tal que las etiquetas a lo largo de la ruta se escriban como s
- Un autómata finito no determinístico puede simularse por medio de:
- Retroceso/Respaldo: (Recorrido Secuencial)
Recordar siguiente configuración alternativa (entrada actual y siguiente estado alternativo) cuando opciones alternativas son posibles
- Paralelismo: (Recorrido en Paralelo)
Rastrear todas las alternativas posibles en paralelo
- Búsqueda hacia adelante:
Buscar más símbolos de entrada para hacerla determinística.
- Retroceso/Respaldo: (Recorrido Secuencial)
Para la simulación de una AFN son necesarias las siguientes operaciones:
- ε-closure:
Conjunto de estados alcanzables sin consumir ningún símbolo de entrada.
- ε-closure(s):
Conjunto de estados alcanzables desde el estado s por las transiciones-ε solamente.
- ε-closure(S):
Conjunto de estados alcanzables desde algún estado s en S por las transiciones-ε solamente.
- move(S, c):
Conjunto de estados hacia los que hay una transición con el símbolo de entrada c desde algún estado s en S.
Reconocimiento de una ER:
- Un AFN es más difícil de simular
- Un AFN es más fácil de construir
- Construir un AFN
- Construir un AFD equivalente
Predefinir los estados alcanzables y precalcular todas las posibles transiciones en vez de simular las transiciones paralelas en tiempo de ejecución
- (opcional) Minimización de Estados
- Simular el AFD
Lex y flex utilizan autómatas finitos no determinísticos
Conclusión
- Los autómatas finitos sólo son capaces de reconocer lenguajes regulares.
- El análisis léxico está basado en expresiones regulares para el reconocimiento de las unidades del lenguaje o tokens.
- El objetivo del reconocimiento de tokens es construir un analizador léxico que produzca tokens y los valores de sus atributos asociados.
- Existen dos métodos para implementar el reconocimiento de tokens: manual o basado en herramientas.
a) El método manual consiste en construir o diseñar y simular autómatas finitos (AF/AEF: Autómata (de Estado) Finito).
b) El método basado en herramientas consiste en usar expresiones regulares para que el generador de código construya los autómatas finitos para el analizador léxico.
- Existen dos tipos de autómatas finitos:
a)Autómatas finitos determinísticos (AFD).
Los cuales se caracterizan por tener a lo más una transición para cada símbolo de entrada.
b)Autómatas finitos no determinísticos (AFN).
Los cuales pueden tener más de una transición para algún símbolo de entrada.
- La simulación de autómatas finitos no determinísticos es más difícil y requiere calcular:
a) ε-closure(S). Es el conjunto de estados alcanzables desde algún estado s en S por las transiciones-ε solamente.
b) move(S, c). Es el conjunto de estados hacia los que hay una transición con el símbolo de entrada c desde algún estado s en S.
- Por otro lado, un autómata finito no determinístico es más fácil de diseñar.
- Sin embargo, un autómata finito no determinístico se puede convertir en un autómata finito determinístico el cual es más fácil de simular.
Te felicito por llegar hasta aquí con ese ímpetu tan incontrolable por saber cada día un poco más, continúa así y no dejes que ese ánimo decaiga. Revisa el material complementario y realiza las actividades correspondientes. Te encuentro próximamente.