Clase4: Transformación desde Expresión regular a Autómata finito determinista

1. DESDE LAS EXPRESIONES REGULARES HASTA LOS AFD

2. AFND AFD EXPRESIÓN REGULAR

3. ER - AFND CONCATENACIÓN ( a.b ) Selección ( a|b ) 1 2 a 3 4 b 1 2 a 3 4 b Ɛ 1 2 a 3 4 b 1 2 a 3 4 b Ɛ Ɛ 5 Ɛ Ɛ

4. ER - AFND Repetición a* 1 2 a 3 Ɛ Ɛ Ɛ Ɛ

5. DESDE UN AFND - AFD Construir cerraduras Ɛ Cerradura Ɛ , es el {} de todos los estados que pueden alcanzar las transiciones Ɛ, desde un estado o estados, se denomina como Una cerradura Ɛ de un estado siempre contiene al mismo estado Eliminación de transiciones múltiples Función mover {} de estados que son alcanzables desde el nuevo estado del conjunto cerradura con cada uno de los caracteres simples. Construir la cerradura de los estados que surgen de la función mover con cada uno de los caracteres Continuar eliminación de transiciones múltiples con la función mover.   Algoritmo

6. Ejemplo     Cerradura Ɛ de un estado: El estado mismo y los estados que conduce una transición Ɛ     1 2 a 3 Ɛ Ɛ Ɛ Ɛ  

7. Ejemplo Construcción de subconjuntos : 1. El estado inicial es el mismo, 2. Cual de los estados conduce con un carácter 1 hacia el 2 = {1,2,3} 3. Desde los estados de {1,2,3} conducen con “a” hacia sí mismo 4. El estado de aceptación contiene el estado de aceptación del AFND 1 2 a 3 Ɛ Ɛ Ɛ Ɛ             a a

8. Ejercicio 2 5 a 6 7 b 1 Ɛ Ɛ 8 Ɛ Ɛ 4 3 Ɛ a Estado (cerradura) a b {1} = {1,2,6}=A Mover(A, a)={3,7} Mover(A, b)={} {3,7} = {3,4,7,8}=B Mover(B, a)={} Mover(B, b)={5} {5} = {5,8} = C Mover(C, a)={} Mover(C, b )={} Estado (cerradura) a b A B B (aceptación) C C (aceptación) A C B b a

9. Ejercicio x ( x|y )*x 1 4 x 5 6 2 x Ɛ 7 Ɛ Ɛ 3 8 Ɛ y Ɛ Ɛ Ɛ Ɛ 9 x Estado (cerradura) X Y {0} = {0}=A Mover(A, x)={1} Mover(A, y)={} {1} = {1,2,3,5,8}=B Mover(B, x)={4,9} Mover(B, y)={6} {4,9} = {4,7,8,2,3,5} = C Mover(C, x)={4,9} Mover(C, y)={6} {6} = {6, 7,8,2,3,5} = D Mover(C, x)={4,9} Mover(C, y)={6}

10. Ejercicio x ( x|y )*x Estado (cerradura) X Y {0} = {0}=A Mover(A, x)={1} Mover(A, y)={} {1} = {1,2,3,5,8}=B Mover(B, x)={4,9} Mover(B, y)={6} {4,9} = {4,7,8,2,3,5,9} = C Mover(C, x)={4,9} Mover(C, y)={6} {6} = {6, 7,8,2,3,5} = D Mover(C, x)={4,9} Mover(C, y)={6} Estado X Y A B B C D C C D D C D X C A B X D Y X Y X Y

11. ANÁLISIS SINTÁCTICO

12. ANÁLISIS SINTÁCTICO Su sintaxis se determina por: Reglas gramaticales de una gramática libre de contexto Operaciones son similares a las expresiones regulares. Con la diferencia de que se debe implementar la recursidad (ciclos repetitivos) Estructura de datos: árboles Algoritmo: Análisis sintáctico ascendente y descendente

13. Gramáticas libres de contexto Es una especificación para la estructura sintáctica de un lenguaje de programación Similar a la estructura léxica reflejada en la expresión regular, solamente que la gramática incluye recursividad