LyA 
96 LyA La tabla de transición de la fig. 3.4 si cumple con la regla : Letra n Dig = Ø Letra n Sub = Ø Dig n Sub = Ø Ø es el conjunto vacío. Los pares p ( s , a ) representados en la tabla se listan enseguida: ( 0 , Letra ) ( 0 , Dig ) ( 0 , Sub ) 1 Error Error ( 1 , Letra ) ( 1 , Dig ) ( 1 , Sub ) 1 1 1 La tabla antes del mapeo de los pares p ( s , a ) a un estado t, estaba vacía, es decir : Simbolos en la entrada Estados LyA En un AFD con columnas c1 , c2 , … , ck donde k es el número de posibles entradas, se debe cumplir: cin cj = Ø , para i ? j Lo anterior es sumamente importante, dado que si no se cumple cin cj = Ø podríamos tener un autómata finito no determinístico. ¿ De dónde salieron estos pares ? 
97 LyA Y … ¿ Cómo se llenan o instancian sus entradas ? LyA Pues precisamente del diagrama del AFD de la fig. 3.3. Por ejemplo, el par ( 0 , Letra ) se puede leer : “Si el estado es el 0, y la lectura en la entrada es una letra, el autómata se moverá al estado 1”. O sea que : move ( 0 , Letra ) = 1 Esta transición es representada por el arco etiquetado por Letra, y que “sale” del estado 0 hacia el estado 1, en el diagrama del AFD. El resultado de la función move ( s , a ) para un automata finito detreminístico es un solo estado ó bien ninguno (caso de error). move ( s,a ) = un solo estado. NINGÚN ESTADO equivale a un error. LyA ……………………… para un AFD. Los move’s que producen error, son los pares: ( 0 , Dig ) y ( 0 , Sub ). move ( 0 , Dig ) = error, move ( 0 , Sub ) = error, ya que en el AFD no hay arco que salga del estado 0 (cero) y que sea etiquetado ya sea por Dig o por Sub. Bueno, pues ya supe como llenar las casillas de la tabla de transición del AFD. 
98 El estado de inicio es el estado 0 y siempre se indica con un arco llegando a dicho estado. Las características que además debe cumplir el AFD son : a) No arcos ?. Si se cumple, dado que no existe un solo arco etiquetado ? con en el diagrama del AFD. b) De los estados 0 y 1, se observan sólo arcos etiquetados en forma única. Nunca se repite una etiqueta para dos o más arcos saliendo de un estado. Existe un algoritmo para simular el funcionamiento de un AFD, al efectuar el reconocimiento o rechazo de una cadena. Fig. 3.5. Utilicemos el algoritmo de la fig. 3.5 para reconocer la cadena iCont1 con el AFD del ejemplo 3.1. La ejecución paso a paso se muestra en la tabla de la fig. 3.6, donde las columnas son variables y sus valores se indican, de acuerdo a la instrucción que se ejecuta en secuencia. LyA 4. s 0 = 0 Estado de inicio del AFD. Sólo tenemos un estado de aceptación y es el denotado con doble círculo : 1. Así, el quinto componente F es: F = {1} La notación de conjuntos es debido precisamente a que F es un conjunto. LyA 
99 Entrada Cadena x terminada en el caracter eof. D (autómata AFD) con estado de inicio s0 y F conjunto de estados finales. Proceso s = s0 c = NextChar ( ) while ( c ? eof ) do s = move ( s , c ) c = NextChar ( ) endwhile if ( s está en F ) then return ‘si’ else return ‘no’ Salida Respuesta ‘si’ si D acepta a x, de otra manera la respuesta es ‘no’. Fig. 3.5. Carta EPS, del algoritmo que simula a un AFD. Fig. 3.6. Reconocimiento de la cadena iCont1. La función NextChar( ) retorna el siguiente caracter de la cadena de entrada x. 
100 El estado de inicio es : s0 = 0, LyA De la tabla fig. 3.6 podemos ver que : move ( 0 , i ) = 1 move ( 1 , C ) = 1 move ( 1 , o ) = 1 move ( 1 , n ) = 1 Dado que s = 1, entonces si pertenece a F, por lo tanto el algoritmo retorna un “si”. El AFD acepta la cadena : iCont ¿ Cómo son obtenidos estos move’s ? 0 1 Letra Inicio 2 4 3 move ( 1 , t ) = 1 move ( 1 , 1 ) = 1 De la tabla de transición del AFD Fig. 3.4. Por ejemplo el move ( 0 , i ) = 1, se lee : “si el autómata se encuentra en el estado 0 y llega una letra -en este caso la i-, el autómata pasa al estado 1. El move ( 1 , 1 ) = 1, se busca en el renglón cuyo estado es 1 y la columna Dig (dígito). Ejemplo 3.2. Existe otro AFD para reconocer el token id del ejemplo 3.1 que no es óptimo, ya que tiene más estados y transiciones que el anterior. Letra Sub Letra Dig Sub Letra Dig Dig Dig Sub Letra Sub Fig. 3.7 AFD para el token id, con 5 estados. 
101 Los estados de aceptación son 4 : El alfabeto es el mismo, es decir : F = { 1, 2, 3, 4 } ? = { A, B, … , Z, a, b, … , z, 0, 1, … , 9 , _ } El conjunto de estados S del AFD, tiene 5 elementos : S = { 0, 1, 2, 3, 4 } La tabla de transición -función move- tiene 5 renglones (todos los estados, tienen al menos un arco saliendo de ellos) y 3 columnas : Símbolos en la entrada Estados En la fig. 3.8 se muestra el trazo del algoritmo que simula al AFD, en el reconocimiento de la cadena X11A_2. 
102 3.3 AUTÓMATA FINITO NO DETERMINÍSTICO (AFND). Un autómata finito no determinístico es un modelo matemático que consiste de : 1. Un conjunto de estados, S. 2. Un conjunto de símbolos de entrada, ? (alfabeto). 3. Una función de transición denominada move, que mapea pares, p ( s , a ) hacia un conjunto de estados. s es un estado y a es un símbolo en la entrada. 4. Un estado de inicio denotado por s0. 5. Un conjunto de estados de aceptación, denotado por F. LyA Fig. 3.8. Simulación del AFD con F = { 1, 2, 3, 4 } Ya que s = 3 y s pertenece a F, el AFD retorna un ……………….. “si” 
103 ….. LyA 1 2 3 ? b a Fig. 3.9 AFND para a + b + En la Fig. 3.9 se muestra el AFND para la expresión regular a+b+.La función move (1 ,a) se define como : move ( 1 , a ) = { 1 , 2 } y move ( 2 , b ) = { 2 , 3 } ¿Hay dos estados a donde el autómata puede efectuar una transición ? Además, un AFND tiene como característica que lo diferencia de un AFD, permitir el uso de arcos etiquetados por el símbolo ?. ? Arcos ? La característica de donde toma el nombre un AFND, consiste en que su función de transición move, mapea los pares p ( s , a ) hacia un conjunto de estados. Revisa el punto 3 para un AFD y vas a encontrar que el autómata determinístico, mapea los pares p(s,a) …. a un sólo estado. !!!! LyA ¿ Qué significa lo anterior ?. Significa que un AFND que se encuentra en un estado s y para un símbolo en la entrada a, pueden existir más de un arcos etiquetados con el símbolo a saliendo del estado s, Fig.3.9. Por lo tanto no está determinada la transición. 1 2 3 a b a b 
104 Los componentes del AFND de la Fig. 3.9 son : El conjunto de estados S = { 1, 2, 3 }, estado inicial s0 = 1 y sólo hay un estado de aceptación F = { 3 }. El alfabeto de entrada es ? = { a, b }. S, s0, F y ? son obtenidos directamente del diagrama que representa el AFND. La tabla de transición es : Símbolos en la entrada Estados move ( 1 , a ) = { 1 , 2 } move ( 1 , b ) = Error move ( 2 , a ) = Error move ( 2, b) = { 2 , 3} Podemos apreciar que el estado 3 no se incluyó en los renglones de estados, ya que no existen arcos que “salgan” de él, o sea, move ( 3 , a ) = Error y move ( 3 , b ) = Error. Ejemplo 3.3 Veamos el correspondiente AFND para el token id en Pascal, de los ejemplos 3.1 y 3.2. Los componentes del AFND son : 0 1 2 LyA Letra En ambos casos la función move nos mapea a 2 estados ¿ A qué estado el autómata efectúa la transición ? ¡ No está determinado ! Por esta razón es un autómata finito no determinístico (AFND). ? Letra | Dig | Sub inicio 
Autómatas Finitos 105 S s0 ? F Ing. Fco. Ríos Acosta = { 1, 2, 3 } = 0 = { A, B, … , Z, a, b, … , z, 0, 1, … , 9 , _, ? } = {2} La función de transición move : Símbolos en la entrada Letra Dig Sub ? Estados 0 {1} – – – 1 {1} {1} {1} {2} Se ha incluído el símbolo ? en la tabla de transición, debido a la característica del AFND que permite arcos -transiciones- etiquetadas por ?. No podemos utilizar el algoritmo de la fig. 3.5 para simular el AFND, pero si podemos efectuar el trazo de la función move cuando se reconoce una cadena. Por ejemplo, si la cadena es iCont, tenemos lo siguiente : i C o n t ? 0 1 1 1 1 1 2 3.4 AUTÓMATAS FINITOS Y EXPRESIONES REGULARES. Existen algoritmos que relacionan la especificación de tokens -expresiones regulares-, con el reconocimiento de éstos -autómatas finitos-. Es posible dada una expresión regular obtener el AFD que reconozca las cadenas del lenguaje denotado por la expresión regular. También es posible obtener el AFND que reconozca el lenguaje representado por dicha expresión regular. “si” acepta la cadena iCont LyA Observa que para este ejemplo, el mapeo de los pares p(s,a) es siempre hacia un sólo estado. En este caso si está determinada la transición, pero el autómata es no determinístico, debido al arco ? del estado 1 al estado 2. 
106 El algoritmo que permite construir el autómata finito determinístico está fuera del alcance de estas notas ( el alumno no tiene los prerequisitos para su estudio en este curso). Sin embargo, el algoritmo utilizado para la construcción del autómata finito no determinístico AFND, es relativamente sencillo de aplicar, ya que se basa en reglas simples. Existen muchas variantes de este algoritmo denominado “Algoritmo de Thompson”. Este algoritmo es dirigido por sintáxis, es decir, usa la estructura sintáctica de la expresión regular para guiar el proceso de construcción del autómata AFND. En la Fig 3.10 se muestra la carta Entrada-Proceso-Salida (EPS) para el algoritmo de construcción de Thompson. Entrada Expresión regular r definida sobre un alfabeto ?. Proceso Primero, reconocemos las subexpresiones que constituyen a r. Usando las reglas (1) y (2), construímos los AFND’s para cada símbolo básico en r. Guiados por la estructura sintáctica de la expresión regular r, combinamos estos AFND´s de manera inductiva usando la regla (3) hasta obtener el AFND para la expresión regular r. Salida Un AFND que reconoce al lenguaje L ( r ). Fig. 3.10 Carta EPS para el algoritmo de construcción de Thompson. Las reglas a las que hace mención el algoritmo de Thompson son las siguientes : 1. Para el símbolo ?, construir el AFND : i es el nuevo estado inicial, y f es el nuevo estado de aceptación. Este AFND reconoce a { ? }. f i inicio ? ALGORITMO DE THOMPSON Expresión Regular Autómata finito no determinístico (AFND) 
107 ? ? ? ? De nuevo, i es el nuevo estado inicial, y f es el nuevo estado de aceptación. Este autómata reconoce { a }. 3. Supongamos que N(s) y N(t) son AFND’s para las expresiones regulares s y t, respectivamente. a) Para la expresión regular s | t (alternancia), construir el siguiente AFND, N(s|t) : i es el nuevo estado inicial, y f es el nuevo estado de aceptación. Se añade una transición ? desde i hacia los estados de inicio de N(s) y de N(t). Además, se añade una transición ? desde los estados de aceptación N(s) y de N(t) hacia el nuevo estado de aceptación f. Los estados de inicio y de aceptación de N(s) y de N(t) no son los estados de inicio y de aceptación del autómata N(s|t). Este AFND reconoce, L(s) U L(t). b) Para la expresión regular st (concatenación), construir el AFND, N(st) : f i i inicio inicio 2. Para cualesquier símbolo a del alfabeto ?, construir el AFND : a N(s) N(t) i inicio f N(s) N(t) f 
108 Ejemplo 3.4. Dada la expresión regular Token (c|d*)a construir su correspondiente AFND. La descomposición sintáctica de la expresión regular consiste de 6 etapas básicamente: c d d* c|d* a (c|d*)a i inicio El estado de inicio de N(s) es ahora el estado de inicio para el AFND N(st), y el estado de aceptación de N(t) se vuelve el estado de aceptación del AFND, N(st). El estado de aceptación de N(s) es mezclado con el estado inicial de N(t); esto significa que todas las transiciones, desde el estado inicio de N(t) son ahora arcos o transiciones desde el estado de aceptación de N(s). El nuevo estado que resulta de esta mezcla, pierde su estatus de estado de inicio o aceptación para el nuevo AFND. El AFND así construido, reconoce el lenguaje L(s) L(t). c) Para la expresión regular s*, construir el AFND, N(s*) : ? f ? i es un nuevo estado inicial, y f es un nuevo estado de aceptación. Con el nuevo AFND se reconoce el lenguaje ( L(s) ) *. ? ? N(s) LyA Orden de aplicación de las reglas. Construiremos 4 AFND’s para cada una de las etapas, hasta llegar al AFND que reconoce : Token AFND para el símbolo c, regla 2 : (c|d*)a 
109 Autómatas Finitos AFND para d*. Primero obtenemos el AFND para el símbolo d (regla 2) : Ahora podemos encontrar la tercera etapa, es decir, c | d * , la alternancia del símbolo c con la cerradura de d : ? ? ? ? ? 4 4 inicio ? ? ? ? ? Luego, seguimos con la construcción del AFND para d* (regla 3c) : ? d d 3 5 3 5 2 2 6 Ing. Fco. Ríos Acosta c inicio 1 0 2 inicio 3 d inicio 0 1 c 7 AFND para d * LyA ? Regla 3 a). c|d* 
? ? 110 Por último, aplicaremos la regla 3b, para concatenar el AFND para c|d* con el AFND del símbolo a: Es buena costumbre, reenumerar los estados en orden progresivo ascendente. De acuerdo a ésto, el AFND que reconoce a la expresión regular Token (c | d*) a es : ( 3.4.1 ) a ? ? ? ? 4 ? ? ? d 3 5 2 6 inicio 0 1 AFND para a c 9 7y8 8 inicio 9 a a ? ? ? ? 3 ? ? ? d 5 6 4 0 inicio 1 2 c 7 8 ? LyA ? Los estados 7 y 8 se unieron para formar uno sólo. Tienes que ponerle un número de estado único. !!! 
111 Cualquier AFND construido con el Algoritmo de Thompson, tiene como característica que existe sólo un estado de inicio y sólo un estado de aceptación. Además, del estado de aceptación nunca “sale” o existe una transición. Los componentes para el AFND que reconoce ( c | d* ) a son : s0 F S ? = = = = 0 ; estado inicial. { 8 } ; estado de aceptación. { 0, 1, 2, 3, 4, 5, 6, 7, 8 } ; conjunto de estados que forman el AFND. { ?, c, d, a } Función de transición move( s , a ) : Símbolos en la entrada Estados Ejemplo 3.5. Dada la expresión regular : Letra Dig Sub Id ? ? ? ? A|B|…|Z|a|b|…|z 0|1|…|9 _ (Letra ) ( Letra | Dig | Sub ) * Construir el AFND correspondiente. Iniciemos observando, que la expresión regular Id consiste de la concatenación de la expresión regular Letra, con la cerradura de una alternancia de las 3 expresiones regulares : Letra, Dig y Sub. 
112 La descomposición sintáctica es la siguiente : Letra Dig Sub Letra | Dig Letra | Dig | Sub ( Letra | Dig | Sub ) * El AFND para letra es construido dos veces, en forma separada. En lo anterior hace hincapié el algoritmo de Thompson. Se construye dos veces, dado que la expresión regular Letra aparece en dos operaciones : La misma regla 2 es aplicada para obtener el AFND para las expresiones regulares Dig y Sub : 4 inicio 5 Dig ( 3.5.3 ) 0 inicio 1 ( Letra ) ( Letra | Dig | Sub ) * El AFND para letra es construido con la regla 2 : Letra 2 3 Así pues, obtengamos el otro AFND para la expresión regular Letra. Letra inicio LyA Tenemos que construir 7 autómatas para encontrar el AFND deseado. ( 3.5.1 ) LyA Concatenación y la alternancia ( Letra ) ( Letra | Dig | Sub ) * ( 3.5.2 ) 
113 Autómatas Finitos Apliquemos ahora la regla 3 c) al AFND 3.5.6, y encontraremos la cerradura ( Letra | Dig | Sub ) * : 6 7 Ing. Fco. Ríos Acosta Sub inicio ( 3.5.4 ) ? ? ? 4 5 ? Dig 2 3 La regla 3a) se aplica sobre los AFND’s 3.5.2 y 3.5.3 para obtener Letra | Dig : Letra 8 inicio 9 ( 3.5.5 ) ? inicio ? ? ? ? ? ? ? 4 5 Dig 2 3 El AFND para Letra | Dig | Sub es encontrado con la regla 3 a) y los autómatas (3.5.4) y (3.5.5) : Letra 8 9 6 7 Sub 11 10 ( 3.5.6 ) 12 inicio ? ? ? ? 13 ? ? ? ? ? 4 5 Dig 2 3 Letra 8 9 ? 6 7 Sub ? 11 ? 10 ( 3.5.7 ) 
114 Los componentes del AFND construido mediante el algoritmo de Thompson : s0 S ? F = = = = 0 { 0,1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12 } { A, B, … , Z, a, b, … , z, 0, 1, … , 9 , _ } { 12 } Función move (s,a) : ( 3.5.8 ) Letra ? ? Sólo hace falta encontrar la concatenación de Letra con (Letra|Dig|Sub)*. Los AFND’s involucrados son el 3.5.1 y 3.5.7. Los estados 1 y 12 se mezclan regla 3 b). ? Letra 13 ? ? ? ? ? 4 5 Dig 2 3 8 9 ? 6 7 Sub ? 11 ? 10 0 inicio 10 1 Letra ? ? ? 12 ? ? ? ? ? 6 7 Dig 4 5 1 y 12 ? Es recomendable reenumerar los estados del AFND. ? Letra 3 8 ? 9 Sub ? 11 ? 2 0 inicio 
Dig Dig . 115 Autómatas Finitos LyA Ing. Fco. Ríos Acosta Símbolos en la entrada Estados Ejemplo 3.6. Construir el AFND que reconoce la definición regular : Dig NumEsp 0 | 1 | … | 9 Dig+.Dig+ NumEsp es una expresión regular que denota al lenguaje formado por las cadenas que son números con punto decimal y al menos una cifra entera y una cifra en la fracción. La descomposición sintáctica de la expresión regular NumEsp, es una concatenación de 3 subexpresiones regulares : Dig+ • + // Cerradura positiva de Dig // Caracter punto // Cerradura positiva de Dig Tenemos que construir 7 autómatas para llegar a la solución : Dig Dig+ . + Dig Dig+ Dig+ . Dig+ Pero sabemos que : r+ = r r* Y … ¿ Cómo encuentro Dig + ? ¡¡ No existe regla !! 
116 Por lo tanto, podemos descomponer Dig+ en : Dig + = Dig Dig * Así, los AFND’s que debemos obtener son los siguientes : Dig Dig * Dig Dig * // Dig + . Dig Dig * . Dig . 5 6 La regla 3 b es para DigDig* . Los estados 4 y 5 se mezclan al efectuar la concatenación : AFND para el símbolo “.” LyA Orden de construcción de los AFND’s. Dig Dig 1 ? Dig * Dig Dig * // Dig + Dig Dig * . Dig Dig * Aplicando reglas 2, 3 c) y 3 b), tenemos el AFND para Dig+ : ? ? 3 4 2 0 inicio Dig ? Dig* ( 3.6.1 ) = Dig+
96 LyA La tabla de transición de la fig. 3.4 si cumple con la regla : Letra n Dig = Ø Letra n Sub = Ø Dig n Sub = Ø Ø es el conjunto vacío. Los pares p ( s , a ) representados en la tabla se listan enseguida: ( 0 , Letra ) ( 0 , Dig ) ( 0 , Sub ) 1 Error Error ( 1 , Letra ) ( 1 , Dig ) ( 1 , Sub ) 1 1 1 La tabla antes del mapeo de los pares p ( s , a ) a un estado t, estaba vacía, es decir : Simbolos en la entrada Estados LyA En un AFD con columnas c1 , c2 , … , ck donde k es el número de posibles entradas, se debe cumplir: cin cj = Ø , para i ? j Lo anterior es sumamente importante, dado que si no se cumple cin cj = Ø podríamos tener un autómata finito no determinístico. ¿ De dónde salieron estos pares ? 97 LyA Y … ¿ Cómo se llenan o instancian sus entradas ? LyA Pues precisamente del diagrama del AFD de la fig. 3.3. Por ejemplo, el par ( 0 , Letra ) se puede leer : “Si el estado es el 0, y la lectura en la entrada es una letra, el autómata se moverá al estado 1”. O sea que : move ( 0 , Letra ) = 1 Esta transición es representada por el arco etiquetado por Letra, y que “sale” del estado 0 hacia el estado 1, en el diagrama del AFD. El resultado de la función move ( s , a ) para un automata finito detreminístico es un solo estado ó bien ninguno (caso de error). move ( s,a ) = un solo estado. NINGÚN ESTADO equivale a un error. LyA ……………………… para un AFD. Los move’s que producen error, son los pares: ( 0 , Dig ) y ( 0 , Sub ). move ( 0 , Dig ) = error, move ( 0 , Sub ) = error, ya que en el AFD no hay arco que salga del estado 0 (cero) y que sea etiquetado ya sea por Dig o por Sub. Bueno, pues ya supe como llenar las casillas de la tabla de transición del AFD. 98 El estado de inicio es el estado 0 y siempre se indica con un arco llegando a dicho estado. Las características que además debe cumplir el AFD son : a) No arcos ?. Si se cumple, dado que no existe un solo arco etiquetado ? con en el diagrama del AFD. b) De los estados 0 y 1, se observan sólo arcos etiquetados en forma única. Nunca se repite una etiqueta para dos o más arcos saliendo de un estado. Existe un algoritmo para simular el funcionamiento de un AFD, al efectuar el reconocimiento o rechazo de una cadena. Fig. 3.5. Utilicemos el algoritmo de la fig. 3.5 para reconocer la cadena iCont1 con el AFD del ejemplo 3.1. La ejecución paso a paso se muestra en la tabla de la fig. 3.6, donde las columnas son variables y sus valores se indican, de acuerdo a la instrucción que se ejecuta en secuencia. LyA 4. s 0 = 0 Estado de inicio del AFD. Sólo tenemos un estado de aceptación y es el denotado con doble círculo : 1. Así, el quinto componente F es: F = {1} La notación de conjuntos es debido precisamente a que F es un conjunto. LyA 99 Entrada Cadena x terminada en el caracter eof. D (autómata AFD) con estado de inicio s0 y F conjunto de estados finales. Proceso s = s0 c = NextChar ( ) while ( c ? eof ) do s = move ( s , c ) c = NextChar ( ) endwhile if ( s está en F ) then return ‘si’ else return ‘no’ Salida Respuesta ‘si’ si D acepta a x, de otra manera la respuesta es ‘no’. Fig. 3.5. Carta EPS, del algoritmo que simula a un AFD. Fig. 3.6. Reconocimiento de la cadena iCont1. La función NextChar( ) retorna el siguiente caracter de la cadena de entrada x. 100 El estado de inicio es : s0 = 0, LyA De la tabla fig. 3.6 podemos ver que : move ( 0 , i ) = 1 move ( 1 , C ) = 1 move ( 1 , o ) = 1 move ( 1 , n ) = 1 Dado que s = 1, entonces si pertenece a F, por lo tanto el algoritmo retorna un “si”. El AFD acepta la cadena : iCont ¿ Cómo son obtenidos estos move’s ? 0 1 Letra Inicio 2 4 3 move ( 1 , t ) = 1 move ( 1 , 1 ) = 1 De la tabla de transición del AFD Fig. 3.4. Por ejemplo el move ( 0 , i ) = 1, se lee : “si el autómata se encuentra en el estado 0 y llega una letra -en este caso la i-, el autómata pasa al estado 1. El move ( 1 , 1 ) = 1, se busca en el renglón cuyo estado es 1 y la columna Dig (dígito). Ejemplo 3.2. Existe otro AFD para reconocer el token id del ejemplo 3.1 que no es óptimo, ya que tiene más estados y transiciones que el anterior. Letra Sub Letra Dig Sub Letra Dig Dig Dig Sub Letra Sub Fig. 3.7 AFD para el token id, con 5 estados. 101 Los estados de aceptación son 4 : El alfabeto es el mismo, es decir : F = { 1, 2, 3, 4 } ? = { A, B, … , Z, a, b, … , z, 0, 1, … , 9 , _ } El conjunto de estados S del AFD, tiene 5 elementos : S = { 0, 1, 2, 3, 4 } La tabla de transición -función move- tiene 5 renglones (todos los estados, tienen al menos un arco saliendo de ellos) y 3 columnas : Símbolos en la entrada Estados En la fig. 3.8 se muestra el trazo del algoritmo que simula al AFD, en el reconocimiento de la cadena X11A_2. 102 3.3 AUTÓMATA FINITO NO DETERMINÍSTICO (AFND). Un autómata finito no determinístico es un modelo matemático que consiste de : 1. Un conjunto de estados, S. 2. Un conjunto de símbolos de entrada, ? (alfabeto). 3. Una función de transición denominada move, que mapea pares, p ( s , a ) hacia un conjunto de estados. s es un estado y a es un símbolo en la entrada. 4. Un estado de inicio denotado por s0. 5. Un conjunto de estados de aceptación, denotado por F. LyA Fig. 3.8. Simulación del AFD con F = { 1, 2, 3, 4 } Ya que s = 3 y s pertenece a F, el AFD retorna un ……………….. “si” 103 ….. LyA 1 2 3 ? b a Fig. 3.9 AFND para a + b + En la Fig. 3.9 se muestra el AFND para la expresión regular a+b+.La función move (1 ,a) se define como : move ( 1 , a ) = { 1 , 2 } y move ( 2 , b ) = { 2 , 3 } ¿Hay dos estados a donde el autómata puede efectuar una transición ? Además, un AFND tiene como característica que lo diferencia de un AFD, permitir el uso de arcos etiquetados por el símbolo ?. ? Arcos ? La característica de donde toma el nombre un AFND, consiste en que su función de transición move, mapea los pares p ( s , a ) hacia un conjunto de estados. Revisa el punto 3 para un AFD y vas a encontrar que el autómata determinístico, mapea los pares p(s,a) …. a un sólo estado. !!!! LyA ¿ Qué significa lo anterior ?. Significa que un AFND que se encuentra en un estado s y para un símbolo en la entrada a, pueden existir más de un arcos etiquetados con el símbolo a saliendo del estado s, Fig.3.9. Por lo tanto no está determinada la transición. 1 2 3 a b a b 104 Los componentes del AFND de la Fig. 3.9 son : El conjunto de estados S = { 1, 2, 3 }, estado inicial s0 = 1 y sólo hay un estado de aceptación F = { 3 }. El alfabeto de entrada es ? = { a, b }. S, s0, F y ? son obtenidos directamente del diagrama que representa el AFND. La tabla de transición es : Símbolos en la entrada Estados move ( 1 , a ) = { 1 , 2 } move ( 1 , b ) = Error move ( 2 , a ) = Error move ( 2, b) = { 2 , 3} Podemos apreciar que el estado 3 no se incluyó en los renglones de estados, ya que no existen arcos que “salgan” de él, o sea, move ( 3 , a ) = Error y move ( 3 , b ) = Error. Ejemplo 3.3 Veamos el correspondiente AFND para el token id en Pascal, de los ejemplos 3.1 y 3.2. Los componentes del AFND son : 0 1 2 LyA Letra En ambos casos la función move nos mapea a 2 estados ¿ A qué estado el autómata efectúa la transición ? ¡ No está determinado ! Por esta razón es un autómata finito no determinístico (AFND). ? Letra | Dig | Sub inicio Autómatas Finitos 105 S s0 ? F Ing. Fco. Ríos Acosta = { 1, 2, 3 } = 0 = { A, B, … , Z, a, b, … , z, 0, 1, … , 9 , _, ? } = {2} La función de transición move : Símbolos en la entrada Letra Dig Sub ? Estados 0 {1} – – – 1 {1} {1} {1} {2} Se ha incluído el símbolo ? en la tabla de transición, debido a la característica del AFND que permite arcos -transiciones- etiquetadas por ?. No podemos utilizar el algoritmo de la fig. 3.5 para simular el AFND, pero si podemos efectuar el trazo de la función move cuando se reconoce una cadena. Por ejemplo, si la cadena es iCont, tenemos lo siguiente : i C o n t ? 0 1 1 1 1 1 2 3.4 AUTÓMATAS FINITOS Y EXPRESIONES REGULARES. Existen algoritmos que relacionan la especificación de tokens -expresiones regulares-, con el reconocimiento de éstos -autómatas finitos-. Es posible dada una expresión regular obtener el AFD que reconozca las cadenas del lenguaje denotado por la expresión regular. También es posible obtener el AFND que reconozca el lenguaje representado por dicha expresión regular. “si” acepta la cadena iCont LyA Observa que para este ejemplo, el mapeo de los pares p(s,a) es siempre hacia un sólo estado. En este caso si está determinada la transición, pero el autómata es no determinístico, debido al arco ? del estado 1 al estado 2. 106 El algoritmo que permite construir el autómata finito determinístico está fuera del alcance de estas notas ( el alumno no tiene los prerequisitos para su estudio en este curso). Sin embargo, el algoritmo utilizado para la construcción del autómata finito no determinístico AFND, es relativamente sencillo de aplicar, ya que se basa en reglas simples. Existen muchas variantes de este algoritmo denominado “Algoritmo de Thompson”. Este algoritmo es dirigido por sintáxis, es decir, usa la estructura sintáctica de la expresión regular para guiar el proceso de construcción del autómata AFND. En la Fig 3.10 se muestra la carta Entrada-Proceso-Salida (EPS) para el algoritmo de construcción de Thompson. Entrada Expresión regular r definida sobre un alfabeto ?. Proceso Primero, reconocemos las subexpresiones que constituyen a r. Usando las reglas (1) y (2), construímos los AFND’s para cada símbolo básico en r. Guiados por la estructura sintáctica de la expresión regular r, combinamos estos AFND´s de manera inductiva usando la regla (3) hasta obtener el AFND para la expresión regular r. Salida Un AFND que reconoce al lenguaje L ( r ). Fig. 3.10 Carta EPS para el algoritmo de construcción de Thompson. Las reglas a las que hace mención el algoritmo de Thompson son las siguientes : 1. Para el símbolo ?, construir el AFND : i es el nuevo estado inicial, y f es el nuevo estado de aceptación. Este AFND reconoce a { ? }. f i inicio ? ALGORITMO DE THOMPSON Expresión Regular Autómata finito no determinístico (AFND) 107 ? ? ? ? De nuevo, i es el nuevo estado inicial, y f es el nuevo estado de aceptación. Este autómata reconoce { a }. 3. Supongamos que N(s) y N(t) son AFND’s para las expresiones regulares s y t, respectivamente. a) Para la expresión regular s | t (alternancia), construir el siguiente AFND, N(s|t) : i es el nuevo estado inicial, y f es el nuevo estado de aceptación. Se añade una transición ? desde i hacia los estados de inicio de N(s) y de N(t). Además, se añade una transición ? desde los estados de aceptación N(s) y de N(t) hacia el nuevo estado de aceptación f. Los estados de inicio y de aceptación de N(s) y de N(t) no son los estados de inicio y de aceptación del autómata N(s|t). Este AFND reconoce, L(s) U L(t). b) Para la expresión regular st (concatenación), construir el AFND, N(st) : f i i inicio inicio 2. Para cualesquier símbolo a del alfabeto ?, construir el AFND : a N(s) N(t) i inicio f N(s) N(t) f 108 Ejemplo 3.4. Dada la expresión regular Token (c|d*)a construir su correspondiente AFND. La descomposición sintáctica de la expresión regular consiste de 6 etapas básicamente: c d d* c|d* a (c|d*)a i inicio El estado de inicio de N(s) es ahora el estado de inicio para el AFND N(st), y el estado de aceptación de N(t) se vuelve el estado de aceptación del AFND, N(st). El estado de aceptación de N(s) es mezclado con el estado inicial de N(t); esto significa que todas las transiciones, desde el estado inicio de N(t) son ahora arcos o transiciones desde el estado de aceptación de N(s). El nuevo estado que resulta de esta mezcla, pierde su estatus de estado de inicio o aceptación para el nuevo AFND. El AFND así construido, reconoce el lenguaje L(s) L(t). c) Para la expresión regular s*, construir el AFND, N(s*) : ? f ? i es un nuevo estado inicial, y f es un nuevo estado de aceptación. Con el nuevo AFND se reconoce el lenguaje ( L(s) ) *. ? ? N(s) LyA Orden de aplicación de las reglas. Construiremos 4 AFND’s para cada una de las etapas, hasta llegar al AFND que reconoce : Token AFND para el símbolo c, regla 2 : (c|d*)a 109 Autómatas Finitos AFND para d*. Primero obtenemos el AFND para el símbolo d (regla 2) : Ahora podemos encontrar la tercera etapa, es decir, c | d * , la alternancia del símbolo c con la cerradura de d : ? ? ? ? ? 4 4 inicio ? ? ? ? ? Luego, seguimos con la construcción del AFND para d* (regla 3c) : ? d d 3 5 3 5 2 2 6 Ing. Fco. Ríos Acosta c inicio 1 0 2 inicio 3 d inicio 0 1 c 7 AFND para d * LyA ? Regla 3 a). c|d* ? ? 110 Por último, aplicaremos la regla 3b, para concatenar el AFND para c|d* con el AFND del símbolo a: Es buena costumbre, reenumerar los estados en orden progresivo ascendente. De acuerdo a ésto, el AFND que reconoce a la expresión regular Token (c | d*) a es : ( 3.4.1 ) a ? ? ? ? 4 ? ? ? d 3 5 2 6 inicio 0 1 AFND para a c 9 7y8 8 inicio 9 a a ? ? ? ? 3 ? ? ? d 5 6 4 0 inicio 1 2 c 7 8 ? LyA ? Los estados 7 y 8 se unieron para formar uno sólo. Tienes que ponerle un número de estado único. !!! 111 Cualquier AFND construido con el Algoritmo de Thompson, tiene como característica que existe sólo un estado de inicio y sólo un estado de aceptación. Además, del estado de aceptación nunca “sale” o existe una transición. Los componentes para el AFND que reconoce ( c | d* ) a son : s0 F S ? = = = = 0 ; estado inicial. { 8 } ; estado de aceptación. { 0, 1, 2, 3, 4, 5, 6, 7, 8 } ; conjunto de estados que forman el AFND. { ?, c, d, a } Función de transición move( s , a ) : Símbolos en la entrada Estados Ejemplo 3.5. Dada la expresión regular : Letra Dig Sub Id ? ? ? ? A|B|…|Z|a|b|…|z 0|1|…|9 _ (Letra ) ( Letra | Dig | Sub ) * Construir el AFND correspondiente. Iniciemos observando, que la expresión regular Id consiste de la concatenación de la expresión regular Letra, con la cerradura de una alternancia de las 3 expresiones regulares : Letra, Dig y Sub. 112 La descomposición sintáctica es la siguiente : Letra Dig Sub Letra | Dig Letra | Dig | Sub ( Letra | Dig | Sub ) * El AFND para letra es construido dos veces, en forma separada. En lo anterior hace hincapié el algoritmo de Thompson. Se construye dos veces, dado que la expresión regular Letra aparece en dos operaciones : La misma regla 2 es aplicada para obtener el AFND para las expresiones regulares Dig y Sub : 4 inicio 5 Dig ( 3.5.3 ) 0 inicio 1 ( Letra ) ( Letra | Dig | Sub ) * El AFND para letra es construido con la regla 2 : Letra 2 3 Así pues, obtengamos el otro AFND para la expresión regular Letra. Letra inicio LyA Tenemos que construir 7 autómatas para encontrar el AFND deseado. ( 3.5.1 ) LyA Concatenación y la alternancia ( Letra ) ( Letra | Dig | Sub ) * ( 3.5.2 ) 113 Autómatas Finitos Apliquemos ahora la regla 3 c) al AFND 3.5.6, y encontraremos la cerradura ( Letra | Dig | Sub ) * : 6 7 Ing. Fco. Ríos Acosta Sub inicio ( 3.5.4 ) ? ? ? 4 5 ? Dig 2 3 La regla 3a) se aplica sobre los AFND’s 3.5.2 y 3.5.3 para obtener Letra | Dig : Letra 8 inicio 9 ( 3.5.5 ) ? inicio ? ? ? ? ? ? ? 4 5 Dig 2 3 El AFND para Letra | Dig | Sub es encontrado con la regla 3 a) y los autómatas (3.5.4) y (3.5.5) : Letra 8 9 6 7 Sub 11 10 ( 3.5.6 ) 12 inicio ? ? ? ? 13 ? ? ? ? ? 4 5 Dig 2 3 Letra 8 9 ? 6 7 Sub ? 11 ? 10 ( 3.5.7 ) 114 Los componentes del AFND construido mediante el algoritmo de Thompson : s0 S ? F = = = = 0 { 0,1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12 } { A, B, … , Z, a, b, … , z, 0, 1, … , 9 , _ } { 12 } Función move (s,a) : ( 3.5.8 ) Letra ? ? Sólo hace falta encontrar la concatenación de Letra con (Letra|Dig|Sub)*. Los AFND’s involucrados son el 3.5.1 y 3.5.7. Los estados 1 y 12 se mezclan regla 3 b). ? Letra 13 ? ? ? ? ? 4 5 Dig 2 3 8 9 ? 6 7 Sub ? 11 ? 10 0 inicio 10 1 Letra ? ? ? 12 ? ? ? ? ? 6 7 Dig 4 5 1 y 12 ? Es recomendable reenumerar los estados del AFND. ? Letra 3 8 ? 9 Sub ? 11 ? 2 0 inicio Dig Dig . 115 Autómatas Finitos LyA Ing. Fco. Ríos Acosta Símbolos en la entrada Estados Ejemplo 3.6. Construir el AFND que reconoce la definición regular : Dig NumEsp 0 | 1 | … | 9 Dig+.Dig+ NumEsp es una expresión regular que denota al lenguaje formado por las cadenas que son números con punto decimal y al menos una cifra entera y una cifra en la fracción. La descomposición sintáctica de la expresión regular NumEsp, es una concatenación de 3 subexpresiones regulares : Dig+ • + // Cerradura positiva de Dig // Caracter punto // Cerradura positiva de Dig Tenemos que construir 7 autómatas para llegar a la solución : Dig Dig+ . + Dig Dig+ Dig+ . Dig+ Pero sabemos que : r+ = r r* Y … ¿ Cómo encuentro Dig + ? ¡¡ No existe regla !! 116 Por lo tanto, podemos descomponer Dig+ en : Dig + = Dig Dig * Así, los AFND’s que debemos obtener son los siguientes : Dig Dig * Dig Dig * // Dig + . Dig Dig * . Dig . 5 6 La regla 3 b es para DigDig* . Los estados 4 y 5 se mezclan al efectuar la concatenación : AFND para el símbolo “.” LyA Orden de construcción de los AFND’s. Dig Dig 1 ? Dig * Dig Dig * // Dig + Dig Dig * . Dig Dig * Aplicando reglas 2, 3 c) y 3 b), tenemos el AFND para Dig+ : ? ? 3 4 2 0 inicio Dig ? Dig* ( 3.6.1 ) = Dig+| Página siguiente |