Análisis léxico: Diseño de autómatas de estado finito
Introducción
¡Hola!
Me da gusto encontrarte de nuevo en este ambiente de aprendizaje, espero que te encuentres con mucho ánimo por seguir adelante ya que faltan nuevos e interesantes temas que te servirán en el futuro. Es por ello que te doy la bienvenida a la clase siete del curso.
En esta sesión aprenderemos sobre
¡Empecemos y buena suerte!
Desarrollo del tema
Construir Autómata a partir de ER:
- Algoritmo de McNaughton-Yamada-Thompson
- Convierte una expresión regular en AFN
- RE → AFN (Construcción de Thompson) → AFD (Construcción de subconjunto) → Minimización de estados
- Descomposición en alfabetos básicos y operadores
- Construir AF para alfabetos básicos
- Combinación de AFs por operador
Construir Autómata a partir de ER:
- RE → AFD Transición_de_estado ⇔ position_transition en patrón → Minimización de estados
- Etiquetar símbolos ER con etiquetas de posición
- Obtener árbol de sintaxis del patrón etiquetado
- calcular {nullable, firstpos, lastpos} de subexpresiones
- calcular follow(i)
- s0 = firstpos(root)
- construir función de transición de acuerdo a follow(i)
Construir una AFN:
- ¿Cómo definir un AFN para una expresión regular?
- Simple. Una expresión regular se puede formar por
- Alternancia (|)
- concatenación y
- Repetición (*, +)
- Simple. Una expresión regular se puede formar por
Sólo requerimos saber cómo construir el AFN para un solo símbolo y cómo componer AFNs
AFN para el símbolo a (o ):
Construir AFNs por Alternancia:
Dados dos AFNs N(s) y N(t), el AFN N(s|t) es:
Construir AFNs por Concatenación:
Dados dos AFNs N(s) y N(t), el AFN N(st) es:
Construir AFNs por Repetición:
Dado el AFN N(s), el AFN N(s*) es:
Dado el AFN N(s), el AFN N(s?) es:
Dado el AFN N(s), el AFN N(s+) es:
Propiedades de los AFNs:
- Tienen a lo más el doble de estados que el número de símbolos y operadores en r
- Tienen exactamente un estado inicial y un estado aceptador
- Cada estado tiene a lo más una transición saliente en un símbolo del alfabeto o a lo más dos transiciones salientes ε
- Todas las transiciones “no determinísticas” son introducidas por transiciones ε que se conectan a/desde estados iniciales/finales.
Convertir AFN a AFD:
- Cada estado del AFD (D) corresponde a un conjunto de estados de AFN (N)
- Transformar N en D por medio de construcción de subconjunto
- D estará en el estado {x, y, z} después de leer una cadena dada si y sólo si N podría estar en cualquiera de los estados x, y o z dependiendo de las transiciones que haga
D lleva cuenta de todas las posibles rutas que N podría tomar y las ejecuta en paralelo
Minimización de Número de Estados:
- Cada AFD tiene un único AFD equivalente más pequeño.
- Dado un AFD M, usar división para construir el AFD equivalente mínimo.
- En realidad unimos estados individuales al conjunto más grande de estados, en vez de dividir a lo loco.
Conclusión
Para recordar:
¡Felicidades, estás avanzando muy bien! Espero que el tema te haya gustado y despierte tu interés para seguir investigando sobre ello. Recuerda elaborar y mandar la consigna de esta clase, te espero en la próxima sesión donde aprenderás un tema relevante para tu formación académica. Hasta pronto.