117 NumEsp estados : Dig Dig 1 ? ? ? 3 0 inicio 2 6 . 4y5 Dig Dig ? 8 ? ? ? 11 10 9 inicio Dig ? Dig 1 ? ? ? 3 4 0 2 . 6y7 ? AFND para Dig+ . ( 3.6.2 ) El AFND para Dig Dig*, expresión regular que forma el tercer término en Dig Dig 8 ? Dig+.Dig+, es igual que el AFND (3.6.1) salvo la numeración de ? ? 11 7 inicio 10 9 ? ( 3.6.3 ) Los estados 6 y 7 se mezclan en uno, al aplicar la regla 3 b), para los AFND 3.6.2 y 3.6.3.
118 Los componentes del AFND para la expresión regular NumEsp?Dig+.Dig+ son los que a continuación se mencionan. s0 = 0 S = { 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 } ? = { 0, 1, … , 9,. } F = {9}
Función move (s,a) :
Símbolos en la entrada Estados Dig Dig ? 6 ? ? ? 9 5 8 7 inicio Dig ? Dig 1 ? El AFND pedido ya reenumerados sus estados es: ? ? 3 4 0 2 . LyA ¡ Solución !
119 move (0, .) move (0, ?) move (1, Dig) move (1, .) move (2, .) move (2, ?) = = = = = = Error Error Error Error Error Error Ejemplo 3.7 La definición regular para el token num en
Pascal es : Dig FraccionOpcional ExponenteOpcional Num ? ? ? ? 0 | 1 | … | 9 ( . Dig+ ) ? ( E ( + | – ) ? Dig+ ) ? ( Dig+) ( FraccionOpcional ) ( ExponenteOpcional ) Construir el AFND que reconozca
el lenguaje denotado por la expresión regular Num. La descomposición sintáctica : ¡¡¡ Caray !!! …. Hay muchos autómatas Y faltó expresar el AFND para la concatenación de :
120 AFND para Dig+ : 5 inicio 6 . Dig Dig ? 8 ? ? ? 11 7 inicio 10 9 Dig Dig 1 ? ( Dig+) ( FracciónOpcional ) ( ExponenteOpcional ) . Dig+ es una expresión regular ya conocida por nosotros. Su AFND es obtenido tras de aplicar las reglas 2, 3 c) y 3 b) : ? ? 3 4 2 0 inicio Dig Sigamos con la concatenación FracciónOpcional : AFND para el símbolo “.” ? Dig* .Dig+ perteneciente ( 3.7.1 ) = Dig+ a la expresión regular ( 3.7.2 ) ( 3.7.3 )
121 Sabemos que no hay regla para r ?, pero también sabemos que : r? = r | ? Así ( . Dig+) ? = . Dig+ | ?. Tenemos el AFND para el primer término de la alternancia, falta obtener el AFND para el símbolo ?. ( 3.7.5 ) Y con la regla 3 a, unimos 3.7.4 con 3.7.5, y tenemos el AFND para la alternancia 12 inicio 13 ? Dig Dig 8 ? Efectuamos la concatenación de (3.7.2) y (3.7.3), mezclando los estados 6 y 7 en un solo
estado: ? ? 11 10 9 5 inicio . 6y7 ( 3.7.4 ) LyA ? Pero …… Qué regla aplicamos para obtener : ( . Dig + ) ?
122 ( 3.7.6 ) AFND para ( .Dig+) ? expresión regular FraccionOpcional. Ya tenemos los AFND’s para dos de los tres términos de la concatenación que define a la expresión regular Num. Construyamos el AFND para la subexpresión regular ExponenteOpcional. Pasos en la
construcción del AFND para E ( + | – ) ? : // AFND símbolo ‘E’ ; regla 2. // AFND símbolo ‘+’ ; regla 2. // AFND símbolo ‘-’ ; regla 2. // AFND para + | – ; regla 3 a). 16 18 20 inicio inicio inicio 17 19 21 E + – ? ? ? ? 20 21 – 18 19 + 22 inicio 23 12 13 ? 14 Dig Dig ? 8 ? ? ? 11 10 9 5 inicio . 6y7 15 ? ? ? ?
123 Autómatas Finitos ( 3.7.8 ) ? ? 20 21 – 18 19 Ing. Fco. Ríos Acosta + 22 ? inicio 23 ? 26 24 25 27 ? ? ? ? ? AFND para ( + | – ) ? ; regla 3 a) (+|-)?=(+|-)|? 28 inicio Dig Dig ? 29 ? ? 32 31 30 Reglas 2, 3 c) y 3 b). ? ? 20 21 – 18 19 + 22 ? inicio 23 ? 24 25 27 ? ? ? AFND para E ( + | – ) ?, la concatenación produce la mezcla de los estados 17 y 26 en un sólo estado. Ahora, construyamos el AFND para E ( + | – ) ? Dig + , iniciando por obtener Dig + : ? ? ? 16 E 17,26 ( 3.7.7 )
124 inicio ? ? ? ? 20 21 – 18 19 La aplicación de la regla 3 b) para la concatenación de ( 3.7.7 ) y ( 3.7.8 ) obliga a la mezcla de los estados 27 y 28 en uno solo : + 22 23 24 25 ? ? ? ? 16 E 17,26 27,28 Dig Dig ? ( 3.7.9 ) El AFND que reconoce : ( E ( + | – ) ? Dig + ) ? = E ( + | – ) ? Dig + | ? es encontrado aplicando la regla 1 y 3 a), para el autómata ( 3.7.9 ) y el autómata para el símbolo ? : 29 ? ? ? ? 32 31 30 AFND para : E ( + | – ) ? Dig +
125 Autómatas Finitos Ing. Fco. Ríos Acosta + 18 19 ? ? 22 ? 23 ? 27,28 ? ? ? E ? 20 21 ? 29 30 31 32 16 – Dig ? 17,26 ? 24 25 ? ? ? 35 ? 33 34 ( 3.7.10 ) El AFND que reconoce el token Num, consiste de la concatenación de los AFND’s : 3.7.1 3.7.6 Dig + , FraccionOpcional y 3.7.10 ExponenteOpcional. La Fig. 3.11
muestra a dicho autómata. ? AFND para la expresión regular ExponenteOpcional Dig 36 ? ? inicio
ExponenteOpcional 126 Autómatas Finitos + ? 17 18 ? ? 16 21 ? ? ? ? E ? 19 20 ? 24 25 26 27 28 14 15 – Dig ? ? 22 23 ? ? ? 13 ? 29 30 ? Fig. 3.11 AFND para el token Num, con los estados reenumerados. inicio Dig Dig ? 1 ? Ing. Fco. Ríos Acosta ? ? 3 4 2 0 11 12 ? 4 Dig Dig ? 7 ? ? ? 10 6 9 8 5 . 13 ? ? ? ? 31 Dig ? ? Dig + F raccionOpciona l
127 3.5 EQUIVALENCIA ENTRE UN AFND Y UN AFD. La
naturaleza de un autómata finito no determinístico, hace que la tarea de simularlo en un
programa de
computadora sea muy difícil. Para un símbolo de entrada pueden existir diferentes transiciones estado a estado, es decir, la aceptación de una cadena puede o debe, involucrar diferentes trayectorias y todas ellas deben de probarse para saber si la cadena de entrada es o no , reconocida por el AFND. Dado que las reglas y
algoritmo de construcción de Thompson son susceptibles de ser programados en una computadora, sin que ésto sea de gran complejidad, una buena
estrategia es obtener el AFND que reconozca el
lenguaje denotado por una expresión regular, para luego construir un AFD a partir de un AFND. El algoritmo que construye un AFD dado un AFND, se denomina Construcción de subgrupos. Una vez encontrado el autómata finito determinístico, puede ser optimizado o sea, reducir el número de estados S que lo forman. El algoritmo de construcción de subgrupos tiene como principal tarea, construir una tabla de transición (función move) para el nuevo AFD. Cada estado del AFD es un conjunto de estados del AFND. Además, el algoritmo hace uso de las
operaciones que aparecen en la tabla de la fig. 3.12. ALGORITMO DE THOMPSON ALGORITMO DE CONSTRUCCIÓN DE SUBGRUPOS OPTIMIZACIÓN POR PARTICIONES Expresión Regular AFD reducido AFND AFD
128 Fig. 3.12 Operaciones de soporte para obtener un AFD. Tanto el algoritmo de construcción de subgrupos, como el algoritmo para el
cálculo de la operación auxiliar ?-cerradura(?), se muestra en la fig. 3.13 a) y b). Entrada AFND Autómata finito no determinístico.
Proceso D = ?-cerradura ( so) D es el conjunto de estados del nuevo AFD. Inicialmente los estados calculados en esta cerradura decimos que no están marcados. While ( existe un estado T no marcado en D ) Do Begin Marcar T For ( cada símbolo de entrada a ) Do Begin U = ?-cerradura (move(T,a)) if ( U no está en D ) then añadir U como un estado no marcado a D Dtran[T,a] = U end end Salida Dtran : Tabla de transición del AFD. Fig. 3.13 (a) Algoritmo de construcción de subgrupos. LyA Conversión de un autómata finito : No Determinístico a Determinístico.
129 Entrada T : Cualesquier conjunto de estados del AFND. Proceso Meter todos los estados en T a la pila ?-cerradura (T) = T While ( Pila no está vacia ) Do Begin Sacar t, elemento tope de la pila for ( cada estado u con un arco ? desde t a u ) Do if ( u no está en ?-cerradura (T) ) then Begin añadir u a ?-cerradura (T) meter u a la pila end end Salida ?-cerradura (T) Fig. 3.13 (b) Cálculo de la ?-cerradura. Ejemplo 3.8. Utiliza el algoritmo de construcción de subgrupos, para construir el Bueno, lo primero es dibujar la tabla de transición denominada DTran, la cual es la salida del algoritmo de construcción de subgrupos Fig. 3.14. LyA AFD equivalente al AFND (3.4.1), obtenido en el ejemplo 3.4. ¿ Cómo empiezo ? Los
algoritmos se ven muy feos !!!!
130 Los renglones de la tabla Dtran son los estados del nuevo AFD que vamos a obtener, aplicando el algoritmo de construcción de subgrupos. Debemos tener cuidado, tal y como se establece en la sección 3.1, que los símbolos de entrada c1 , c2 ,.. ck cumplan : ci n cj = Ø , para i ? j En nuestro caso c1= c, c2= d, c3= a : c n d = Ø c n a = Ø d n a = Ø CONSTRUCCIÓN DE SUBGRUPOS Tabla de transición del nuevo AFD : DTran ¡¡¡ Si se cumple !!! AFND Fig. 3.14. Entradas y salidas para el algoritmo de construcción de subgrupos. DTran Símbolos en la entrada Estados LyA Ahh !! , las columnas en la tabla son las posibles entradas ( símbolos del alfabeto ? ), y los renglones son los estados. ¿ Cuáles estados ? !!!
131 Si lo anterior no se cumple, corremos el peligro de construir un AFD que no sea determinístico! o sea, un AFND!, lo cual sería totalmente erróneo ya que precisamente n Además U ci = ? alfabeto de entrada del nuevo AFD menos el símbolo ? , lo cual se i=1 cumple : ? ={a,c,d} Iniciemos con la primera instrucción del algoritmo : ?-cerradura ( s0 ) = ?-cerradura ( s{0} ) La ?-cerradura (s{0}) del estado de inicio nos permite obtener el primer estado del nuevo autómata AFD. Llamémosle A y lo añadimos a D (conjunto de estados del nuevo AFD). A = ?-cerradura (s{0}) (3.8.1) Apliquemos el algoritmo de la fig. 3.13 b) para el cálculo de la ?-cerradura , donde : T = {0} La ?-cerradura ({0}) se inicializa a T : ?-cerradura ({0}) = {0} Realmente, el algoritmo de la Fig. 3.13 b), usa una pila para almacenar
información de estados que “no han sido probados”, es decir, los estados en la pila tienen que ser visualizados para ver si alcanzan con arcos ? algún otro u otros estados. Si es así, estos nuevos estados “alcanzados” son metidos a la pila y añadidos a la ?-cerradura (T). Asimismo estos estados son también “probados” para ver si ellos “alcanzan” a otros estados, y así recurrentemente se repite el proceso, hasta que la pila quede vacía. Para este ejemplo, observemos el AFND 3.4.1. y mostremos gráficamente a los estados que son aceptados con los arcos ? desde
el estado de inicio s0= 0 : 1 0 4 3 6 7 LyA Estos estados constituyen la ?-cerradura ({0})
132 Así, ?-cerradura ({0}) = { 0,1,3,4,6,7 } por lo que el primer estado del nuevo autómata AFD es en realidad el conjunto de estados { 0,1,3,4,6,7 } del AFND : A = { 0,1,3,4,6,7 } Agreguemos este estado así calculado a la tabla de transición Dtran. Símbolos en la entrada Estados {0,1,3,4,6,7} Ahora el conjunto de estados del nuevo AFD D ={A}, tiene un nuevo estado, el primero! Enseguida, el algoritmo de la construcción de subgrupos, establece que hay que obtener la transición que da lugar cuando el AFD se encuentra en el estado A y en la entrada se tiene el símbolo c. Lo mismo se calcula para el símbolo d y el símbolo a. Estas transiciones son los nuevos estados para el AFD que se deberán añadir al conjunto D. Los nuevos estados son calculados mediante la ?-cerradura de las
funciones move para el estado A y cada símbolo en la entrada. B = ?-cerradura ( move(A,c) ) C = ?-cerradura ( move(A,d) ) D = ?-cerradura ( move(A,a) ) Calculemos primeramente a todos los move’s. El move (A,c) es el conjunto de estados del AFND que son alcanzados desde A, al existir en la entrada un símbolo c. Recordemos que A = { 0,1,3,4,6,7 }. Entonces : move ( {0,1,3,4,6,7}, c ) = {2} ya que el estado 2 es alcanzado desde el estado 1 con una entrada c, ( ver autómata 3.4.1), y el estado 1 está en A. move ( {0,1,3,4,6,7}, d ) = {5}
133 Debido a que el estado 5 es alcanzado desde el estado 4, y el estado 4 está en A. move ( {0,1,3,4,6,7}, a ) = {8} En este caso el estado 7 “alcanza” al estado 8, con un arco etiquetado por a. Ahora nos resta obtener las cerraduras sobre estos move’s: B = ?-cerradura ({2}) C = ?-cerradura ({5}) D = ?-cerradura ({8}) Las ?-cerraduras aplicando el algoritmo de la Fig. 3.13 b) son : 2 7 B = ?-cerradura ({2}) = {2,7} 4 5 6 7 C = ?-cerradura ({5}) = {5,4,6,7} 8 D = ?-cerradura ({8}) = {8} B, C y D nuevos estados del AFD. Se añaden estos nuevos estados a D estados: Destados = { A,B,C,D } Y también a la tabla de transición, como renglones. Recordemos que B, C, D son estados a los cuales hay una transición desde el estado A, habiendo un símbolo en la entrada. La tabla de transición DTran tiene ahora nuevos elementos: Símbolos en la entrada Estados {0,1,3,4,6,7} {2,7} {4,5,6,7} {8} ? ? ? ? LyA ¿ Y si alguno de los move’s o todos, fueran iguales ?
134 El algoritmo de construcción de subgrupos dice que el estado A “ya está marcado”, es decir, las transiciones (si existen) del estado A para cada símbolo en la entrada, ya se encontraron. Ahora los estados B, C y D son los que aún no están marcados, o sea que tenemos que encontrar las transiciones del estado B, del C y del D, para cada símbolo en la entrada. De acuerdo a lo anterior, calculemos en primer término las ?-cerraduras de los move’s del estado B = {2,7}. Obtengamos primero los move’s, tal y como lo hicimos anteriormente con el estado A : move ( B,c ) = move ({2,7}, c ) = Ø move ( B,d ) = move ({2,7}, d ) = Ø // vacío // vacío move ( B,a ) = move ({2,7}, a ) = {8} Luego : E = ?-cerradura (vacío) = No existe transición, por lo tanto, tampoco el estado E. F = ?-cerradura (vacío) = No existe transición, por lo tanto, tampoco el estado F. G = ?-cerradura ({8}) = {8}, ya que desde el estado 8 no se alcanza ningún estado con un arco ?. Además, G = D. Y la tabla de transición con estos cambios queda : E = ?-cerradura ( move(B,c) ) F = ?-cerradura ( move(B,d) ) G = ?-cerradura ( move(B,a) ) LyA Estas ?-cerraduras generan 3 nuevos estados si y sólo si, las ?-cerraduras no son vacías. Es decir, sólo la ?-cerradura que no sea = Ø genera un nuevo estado en la tabla Dtran del AFD que se está construyendo.
135 Autómatas Finitos Ing. Fco. Ríos Acosta Símbolos en la entrada Estados {0,1,3,4,6,7} {2,7} {4,5,6,7} {8} Seguimos con el estado C. ?-cerradura ( move(C,c) ) ?-cerradura ( move(C,d) ) ?-cerradura ( move(C,a) ) Sus funciones move son : move (C,c) = move ({4,5,6,7}, c ) = Ø // vacío move (C,d) = move ({4,5,6,7}, d ) = {5} move (C,a) = move ({4,5,6,7}, a ) = {8} y las cerraduras son : ?-cerradura (vacío) = No existe, no hay transición. ?-cerradura ({5}) = {4,5,6,7}, es el estado C. 4 5 6 7 ?-cerradura ({8}) = {8}, es el estado D. Agregamos estas transiciones a la tabla de transición DTran Símbolos en la entrada Estados {0,1,3,4,6,7} {2,7} {4,5,6,7} {8} ? ? ?
136 Lo mismo hacemos para el estado D. ?-cerradura ( move(D,c) ) ?-cerradura ( move(D,d) ) ?-cerradura ( move(D,a) ) Los move’s son: move (D,c) = move ({8}, c) = Ø move (D,d) = move ({8}, d) = Ø move (D,a) = move ({8}, a) = Ø // vacío // vacío // vacío y las cerraduras también son vacías, es decir, del estado D a otro estado no existen transiciones. Símbolos en la entrada Estados {0,1,3,4,6,7} {2,7} {4,5,6,7} {8} El estado D puede eliminarse de la tabla de transición dado que no tiene transiciones a otro estado. Símbolos en la entrada Estados {0,1,3,4,6,7} {2,7} {4,5,6,7} Tabla de transición D tran del autómata finito determinístico AFD, resultado de aplicar el algoritmo de construcción de subgrupos. LyA
137 A B C D = = = = {0,1,3,4,6,7} {2,7} {4,5,6,7} {8} // // // // No contiene al estado 8. No contiene al estado 8. No contiene al estado 8. Si lo contiene. Por lo tanto, D es el estado (en este caso, el único) de aceptación del nuevo AFD. Ejemplo 3.9. Dado el autómata finito no determinístico AFND ( 3.5.8 ) del ejemplo 3.5. obtener su correspondiente AFD aplicando el algoritmo de construcción de subgrupos. Iniciamos con las columnas por la tabla Dtran. Símbolos en la entrada Letra Dig Sub Estados . . . . Es fácil ver que : Letra n Dig = Ø Letra n Sub = Ø = Ø Dig n Sub LyA ¡¡¡ Ya hicimos lo primero !!! LyA A Con la tabla DTran así obtenida, podemos mostrar el
diagrama del AFD. El estado de inicio del nuevo AFD siempre será A, es decir la ?-cerradura (s0). B C c d inicio a a a D aceptación del AFND. d Como sufrí para obtenerlo !!!
6 138 move (A,Dig) = move ({0},Dig) = Ø move (A,Sub) = move ({0},Sub) = Ø // // vacío vacío Sólo la ?-cerradura (move(A,letra)) es diferente al conjunto vacío. Vamos a obtenerla : B = ?-cerradura ({1}) = { 1,2,3,4,6,9,12 } 1 3 9 2 12 ? ? ? ? ? 4 ? Ahora, tenemos que encontrar los estados que forman al conjunto D y añadirlos junto a sus transiciones, a la tabla de transición Dtran. El primer estado del nuevo AFD ( estado de inicio ) es : A = ?-cerradura (s0 ) donde s0 es el estado de inicio del AFND. La ?-cerradura ({0}) se obtiene aplicando el algoritmo de la Fig. 3.13 b). A = ?-cerradura ({0}) = {0} Calculamos las transiciones del estado A, cuando en la entrada se tiene una letra o un dígito o bien un subrayado. ?-cerradura ( move (A,letra) ) ?-cerradura ( move (A,Dig) ) ?-cerradura ( move (A,Sub) ) Sus funciones move son : move (A,letra) = move ({0},letra) = {1} LyA Esta ?-cerradura constituye al nuevo estado del AFD : B = {1,2,3,4,6,9,12 }
139 move( {1,2,3,4,6,9,12} , Letra ) = {5} ?-cerradura ({5}) = {5,8,11,2,3,4,9,6,12} ? ? C = {2,3,4,5,6,8,9,11,12} move ( {1,2,3,4,6,9,12},Dig ) = {7} ?-cerradura ({7}) = {7,8,11,2,3,4,6,9,12} // El estado 6 alcanza al 7. Ver AFND 3.5.8 // Nuevo estado 5 8 11 2 12 Llamémosle C al nuevo estado del AFD, • ?-cerradura ( move(B,Dig) ) 3 9 // El estado 4 alcanza al 5. Ver AFND 3.5.8 // Nuevo estado 4 6 LyA • ?-cerradura ( move(B,Letra) ) La tabla de transición Dtran después de añadir los estados A y B y las transiciones de A, se muestran enseguida. Símbolos en la entrada Estados {0} {1,2,3,4,6,9,12} El estado A, se dice que está “marcado”, ya que sus transiciones para los símbolos de entrada fueron calculados. El estado B no está “marcado”, pues falta calcular las transiciones, que posiblemente nos lleven a nuevos estados. Pues … calculemos las transiciones para el estado B.
140 ? ? ? 7 8 11 2 ? 12 • ?-cerradura (move(B,Sub)) move({1,2,3,4,6,9,12},Sub) = {10} ?-cerradura ({10}) = {10,11,2,3,4,6,9,12} 3 9 4 6 ? 10 11 2 12 Ahora, el AFD tiene ya 5 estados : DEstados = { A,B,C,D,E }. Sumemos estos nuevos estados a Dtran, además de las transiciones de B con cada símbolo en la entrada. Símbolos en la entrada Estados {0} {1,2,3,4,6,9,12} {2,3,4,5,6,8,9,11,12} {2,3,4,6,7,8,9,11,12} {2,3,4,6,9,11,12} Los estados A y B ya están marcados. Los estados C, D y E no lo están, de acuerdo al algoritmo de construcción de subgrupos. Esto quiere decir, que es necesario calcular las transiciones de los estados C, D y E para cada símbolo en la entrada. Transiciones del estado C. • ?-cerradura ( move(C,Letra) ) 3 9 D = {2,3,4,6,7,8,9,11,12} // El estado 9 alcanza al 10. Ver AFND 3.5.8 // Nuevo estado 4 6 E = {2,3,4,6,9,11,12}
141 Autómatas Finitos Ing. Fco. Ríos Acosta move ({2,3,4,5,6,8,9,11,12},Letra) = {5} // Estado C ?-cerradura ({5}) = {5,8,11,2,3,4,9,6,12} • ?-cerradura ( move(C,Dig) ) move ({2,3,4,5,6,8,9,11,12},Dig) = {7} ?-cerradura ({7}) = Estado D • ?-cerradura ( move(C,Sub) ) move ({2,3,4,5,6,8,9,11,12},Sub) = {10} // Ya calculado. Este move nos lleva al estado D. // Ya calculado. Este move nos lleva al estado E. ?-cerradura ({10}) = Estado E La tabla Dtran con las anteriores transiciones ya incluídas es : Símbolos en la entrada Estados {0} {1,2,3,4,6,9,12} {2,3,4,5,6,8,9,11,12} {2,3,4,6,7,8,9,11,12} {2,3,4,6,9,11,12} Transiciones estado D. • ?-cerradura (move(D,Letra)) // Ya calculado. Este move nos lleva al estado C. move ({2,3,4,6,7,8,9,11,12},Letra) = {5} ?-cerradura ({5}) = Estado C • ?-cerradura (move(D,Dig)) // // Ya calculado. Este move nos lleva al estado D. Ya calculado. Este move nos lleva al estado E. move ({2,3,4,6,7,8,9,11,12},Dig) = {7} ?-cerradura ({7}) = Estado D • ?-cerradura (move(D,Sub)) move ({2,3,4,6,7,8,9,11,12},Sub) = {10} ?-cerradura ({10}) = Estado E
