142 // // Ya calculado. Este move nos lleva al
estado C. Ya calculado. Este move nos lleva al estado D. Transiciones estado E. • ?-cerradura (move(E,Letra)) move ({2,3,4,6,7,8,9,11,12},Letra) = {5} ?-cerradura ({5}) = Estado C • ?-cerradura (move(E,Dig)) move ({2,3,4,6,7,8,9,11,12},Dig) = {7} ?-cerradura ({7}) = Estado D • ?-cerradura (move(E,Sub)) // Ya calculado. Este move nos lleva al estado E. move({2,3,4,6,7,8,9,11,12},Sub) = {10} ?-cerradura ({10}) = Estado E LyA Incluímos estas transiciones del estado D en la tabla Dtran :
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} Sólo falta obtener las transiciones para
el estado E.
Autómatas Finitos 143 La tabla Dtran Ing. Fco. Ríos Acosta del nuevo AFD queda : Símbolos en la entrada ( 3.9.1 ) El AFD tiene 4 estados de aceptación : B, C, D y E debido a que la regla establece que : Dig Sub Dig Letra A inicio B D Sub E 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} Todos los estados A, B, C, D y E están “marcados”, es decir, sus transiciones han sido calculadas. El
algoritmo de LyA Letra Letra
construcción de subgrupos ha terminado. El
diagrama del nuevo autómata se construye a partir de la tabla de transición Dtran. Letra C Letra Dig Dig Sub
144 • si un estado s del nuevo AFD contiene al estado final f del AFND, s será un estado de aceptación. B = C = D = E = {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,10,11,12} Dig ? [ 0-9 ] Token ? (Cons*) (Tres) (Vocal) (Letra*) Dig De inicio, debemos identificar los símbolos en la entrada. Un error común es seleccionar las siguientes columnas para la tabla Dtran : inicio LyA Los cuatro estados del AFD : B,C,D y E, contienen al estado 12 !!. • El estado final del AFND original es 12. Ver autómata 3.5.8 Vocal Letra ? 5 ? ? ? 4 7 6 ? ( 3.10.1 ) El AFND reconoce la expresión regular : Cons ? [ B-DF-HJ-NP-TV-Zb-df-hj-np-tv-z ] Vocal ? [ A,a,E,e,I,i,O,o,U,u ] Letra ? Cons | Vocal Tres ? 4 | 6 | 8 Cons 0 ? Ejemplo 3.10. Encuentra el AFD para el siguiente AFND : ? ? 3 1 4|6|8 9 8 Dig 2
145 Autómatas Finitos Ing. Fco. Ríos Acosta Símbolos en la entrada Estados Cons Vocal Letra Tres Dig Tres n Dig ? Ø y no se cumple la regla : ci n cj = Ø ; para i ? j …. ( r1 ) La correcta
selección es la mostrada en la siguiente tabla Dtran : Símbolos en la entrada Estados Cons Vocal Tres Otros Otros = {0,1,2,3,5,7,9} ¿ Cuál error ? LyA 5 La
igualdad U L (ci) = S si cumple ya que : i=1 L (Cons) U L (Vocal) U L (Letra) U L (Tres) U L(Dig) = S Alfabeto de entrada y S = {A, B,…, Z, a, b,…, z, 0, 1,…, 9} Pero la intersección entre ellos, en algunos, no es el conjunto vacío. Es decir : Cons n Letra ? Ø Vocal n Letra ? Ø
Podemos comprobar fácilmente que U L ( ci) = S 146 Autómatas Finitos i=1 : S = L (Cons) U L (Vocal) U L (Tres) U L(Otros) Añadimos A en la tabla Dtran move ({0,1,3},Cons) = {2} // Desde 1 alcanzamos el estado 2 con una consonante. Ver AFND 3.10.1. Ing. Fco. Ríos Acosta 4 0 3 Luego, se calculan las transiciones del estado A para cada símbolo en la entrada. Transiciones estado A. • ?-cerradura (move(A,Cons)) LyA Alfabeto de entrada Y la regla r1 se cumple. La dificultad ha sido salvada, debemos ahora iniciar con el algoritmo de construcción de subgrupos : Recuerda que el primer paso es obtener : A = ?-cerradura ( s 0 ) A es el estado inicial del nuevo AFD A = ?-cerradura ({0} = {0,1,3} Símbolos en la entrada Estados {0,1,3} 1
147 // Nuevo estado B // // ver AFND 3.10.1 No se genera nuevo estado. move ({0,1,3},Vocal) = Ø ?-cerradura (move(A,Vocal)) = “No existe” • ?-cerradura (move(A,Tres)) // Del estado 3 alcanzamos al estado 4, con una
lectura en la entrada de 4 | 6 | 8. Ver AFND 3.10.1. // Nuevo estado C move ({0,1,3},Tres) = {4} ?-cerradura ({4}) = {4} • ?-cerradura (move(A,Otro)) move ({0,1,3},Otro) = Ø ?-cerradura (move(A,Otro)) = “No existe” // ver AFND 3.10.1 // No se genera nuevo estado. LyA Transiciones para B. ?-cerradura ({2}) = {2,3,1} 1 2 3 • ?-cerradura (move(A,Vocal)) Añadimos las transiciones del estado A, y los nuevos estados B y C, a la tabla Dtran. Símbolos en la entrada Estados {0,1,3} {2,3,1} {4} Ahora, debemos calcular las transiciones de los estados B y C para cada símbolo en la entrada. Aquí, podremos encontrar nuevos estados !!.
148 // Este move nos lleva al estado B • ?-cerradura (move(B,Cons)) move ({1,2,3},Cons) = {2} ?-cerradura ({2}) = Estado B • ?-cerradura (move(B,Vocal)) // No hay transición // Error move ({1,2,3}, Vocal) = Ø ?-cerradura (move(B,Vocal)) = “No existe” • ?-cerradura (move(B,Tres)) // Estado C move ({1,2,3}, Tres) = {4} ?-cerradura ({4}) = Estado C • ?-cerradura (move(B,Otros)) move ({1,2,3}, Otros) = Ø ?-cerradura (move(B, Otros)) = “No existe” // No hay transición // Error Símbolos en la entrada Estados {0,1,3} {2,3,1} {4} Dtran con las transiciones para el estado B añadidos. Transiciones para C. • ?-cerradura (move(C,Cons)) // No hay transición // Error move ({1,2,3}, Cons) = Ø ?-cerradura (move(C, Cons)) = “No existe” • ?-cerradura (move(C,Vocal)) move ({4},Vocal) = {5} // El estado 4 alcanza al estado 5, con una entrada vocal. Ver AFND 3.10.1. // Nuevo estado D move ({4}, Tres) = Ø // No hay transición ?-cerradura ({5}) = {5,6,8} 6 5 • ?-cerradura (move(C,Tres)) 8
149 ?-cerradura (move(C, Tres)) = “No existe” • ?-cerradura (move(C,Otros)) move ({4}, Otros) = Ø ?-cerradura (move(C, Otros)) = “No existe” // Error // No hay transición // Error Añadimos estas transiciones del estado C a la tabla Dtran : Símbolos en la entrada Estados {0,1,3} {2,3,1} {4} {5,6,8} Dtran con las transiciones del estado C añadidas. Ahora los estados A, B y C ya están “marcados” según el algoritmo de construcción de subgrupos. El estado D aún no está marcado, por lo tanto, tenemos que calcular sus transiciones. Transiciones para D. • ?-cerradura (move(D,Cons)) // El estado 6 alcanza al estado 7, con una entrada Cons. Observar que Cons ? Letra Ver AFND 3.10.1. // Nuevo estado E // El estado 6 alcanza al estado 7, con una entrada Vocal. Observar que Vocal ? Letra. Ver AFND 3.10.1. // El estado 8 alcanza al estado 9, con move ({5,6,8}, Cons) = {7} ?-cerradura ({7}) = {6,7,8} 6 7 8 • ?-cerradura (move(D,Vocal)) move ({5,6,8}, Vocal) = {7} ?-cerradura ({7}) = Estado E • ?-cerradura (move(D,Tres)) move ({5,6,8}, Tres) = {9}
150 ?-cerradura ({9}) = {9} una entrada 4|6|8. Observa que Tres ? Dig .Ver AFND 3.10.1. // Nuevo estado F • ?-cerradura (move(D,Otros)) move ({5,6,8}, Otros) = {9} // El estado 8 alcanza al estado 9, con una entrada 0|1|2|3|5|7|9 . Observa que Otros ? Dig . Ver AFND 3.10.1. LyA Transiciones para E. ?-cerradura ({9}) = Estado F Símbolos en la entrada Estados {0,1,3} {2,3,1} {4} {5,6,8} {6,7,8} {9} Dtran con la transicióm del estado D añadidos. Y … ¿ Ésto nunca acaba ? !!! LyA El algoritmo de construcción de subgrupos termina hasta que todos los estados en DEstados estén marcados, es decir, hasta que las transiciones para dichos estados estén calculadas. Entonces, aún no hemos terminado, ya que falta de calcular las transiciones para los nuevos estados E y F .
151 // // Este move nos lleva al estado E // Este move nos lleva al estado E // Este move nos lleva al estado F // Este move nos lleva al estado F Transición no existe • ?-cerradura (move(E,Cons)) move ({6,8,7}, Cons) = {7} ?-cerradura ({7}) = Estado E • ?-cerradura (move(E,Vocal)) move ({6,8,7}, Vocal) = {7} ?-cerradura ({7}) = Estado E • ?-cerradura (move(E,Tres)) move ({6,8,7}, Tres) = {9} ?-cerradura ({9}) = Estado F • ?-cerradura (move(E,Otros)) move ({6,8,7}, Otros) = {9} ?-cerradura ({9}) = Estado F Transiciones para F. • ?-cerradura (move(F,Cons)) move ({9}, Cons) = Ø • ?-cerradura (move(F,Vocal)) move ({9}, Vocal) = Ø • ?-cerradura (move(F,Tres)) move({9}, Tres) = Ø • ?-cerradura (move(F,Otros)) move ({9}, Otros) = Ø // Transición no existe // Transición no existe // Transición no existe Símbolos en la entrada Estados {0,1,3} {2,3,1} {4} {5,6,8} {6,7,8} {9} Ahora, todos los estados están marcados. En el anterior
cálculo de transiciones para E y F no se generaron nuevos estados.con la transicióm nos estado Ees Fconstruir el nuevo AFD a Dtran Lo único quedel resta y añadidos.
152 partir de Dtran , pero antes simplificamos la tabla de transición, eliminando el estado F ya que no produce ninguna transición, es decir, no existen arcos que “salgan” de él. Símbolos en la entrada Estados {0,1,3} {2,3,1} {4} {5,6,8} {6,7,8} Analicemos los estados del nuevo AFD : A B C D E F = = = = = = {0,1,3} {1,2,3} {4} {5,6,8} {6,7,8} {9} // Estado de aceptación del nuevo AFD. El único estado del nuevo AFD que contiene al estado 9 de aceptación del AFND es el F. Por lo tanto, el nuevo AFD sólo tiene un estado de aceptación : estado F. Cons Cons 4|6|8 4|6|8 B E A C D F inicio 4|6|8 4|6|8 Vocal Vocal Cons Vocal Cons Otros Otros ( 3.10.2 )
153 3.6 OPTIMIZACIÓN DE UN AUTÓMATA FINITO DETERMINÍSTICO AFD. Cualesquier conjunto regular (aquél que es denotado por una expresión regular), es reconocido por un AFD, con un mínimo de estados. En esta sección mostraremos como construir un AFD reducido su conjunto S de estados, a un número óptimo, sin afectar
el lenguaje que éste reconoce. El algoritmo que optimiza el número de estados de un AFD se le denomina algoritmo por particiones, Fig. 3.15. Dig Cons Letra Dig Tres A B C D E F inicio Tres Vocal El autómata puede simplificarse en sus transiciones del estado D a E, del E al E, E a F y D a F ya que : Cons | Vocal = Letra 4 | 6 | 8 | Otros = Dig El AFD que reconoce la expresión regular es : Cons Letra LyA ¡¡ Puff !!! …. Hasta que terminamos.
154 S = {a,b} // Alfabeto de entrada A C B D E inicio b Entrada AFD
Proceso 1. Construir una partición inicial ? del conjunto S de estados del AFD, con dos
grupos : El de estados de aceptación F y el de los estados de no aceptación S-F. 2. Obtener una nueva partición ?nueva a partir de ? aplicando el sig.
procedimiento : for ( cada
grupo G de ? ) Do Begin Particionar G en subgrupos, tales que 2 estados s y t de G estén en el mismo subgrupo si y solo si para todos los símbolos a de entrada, los estados s y t tienen transiciones para a hacia estados en el mismo grupo de ?. Reemplazar G en ?nueva por el conjunto de todos los subgrupos formados End 3. Si ?nueva = ?, entonces ?final = ? y continuar con la etapa 4. De otra manera repetir la etapa (2) con ? := ?nueva. 4. Seleccionar un estado de cada grupo de la partición final ?final como el estado representativo de ese grupo. Los estados representativos serán los estados del nuevo AFD mínimo u óptimo. Salida AFD mínimo Fig. 3.15 Algoritmo de partición para optimizar un AFD. Ejemplo 3.11 Utilizando el algoritmo de partición, reduce u optimiza al siguiente AFD que reconoce la expresión regular (a | b)*abb. b b b b a a a Identifiquemos los componentes del AFD. a a ( 3.11.1 )
155 // Estado de inicio // Estados de aceptación // Estados del autómata Símbolos en la entrada s0 = A F = {E} S = {A,B,C,D,E}
Función move (s,a) Estados El primer paso del algoritmo es la construcción de la partición inicial ? del conjunto S del AFD. Esta partición ? consta de dos grupos : G1 = {E} G2 = {A,B,C,D} // Estados de aceptación; conjunto F del AFD // Otros estados S-F LyA ( 3.11.2 ) Iniciaré la aplicación del algoritmo de partición. Podemos denotar la partición inicial ? de la siguiente manera : ? = { (E) , (ABCD) } 2o. Paso. Obtener una nueva partición ?nueva. , pero …. LyA partición.
156 Ahí, en ?nueva se añade G1. ?nueva = { (E) }. Veamos ahora el grupo G2 = (ABCD). • Transiciones con símbolo a de los estados en G2. : En todos los estados su transición es hacia el estado B, y este estado forma parte del grupo, por lo tanto, NO HAY PARTICIÓN POSIBLE. A B C D B B B B • Transiciones con el símbolo b de los estados en G2 : A B C C D C b D E En este caso, los estados A, B y C transicionan hacia un estado perteneciente al grupo G2, pero el estado D tiene una transición a un estado E que no forma parte de este grupo G2. Por lo tanto SI HAY PARTICIÓN y ésta es : a a a a b b b El grupo G1 = (E) no es posible particionarlo y es obvio debido a que tiene un sólo estado. Un grupo con un sólo estado, no puede particionarse !!! LyA
157 G21 = (ABC) G22 = (D) Con ? = { (E), (ABC), (D) }, el grupo que puede aceptar ser particionado es : (ABC). Analicemos las transiciones de los estados de este grupo para cada símbolo en la entrada: LyA Agregamos estos nuevos grupos a ?nueva : ?nueva = { (E) , (ABC) , (D) } La nueva partición ahora tiene 3 grupos : G1 = (E), G2 = (ABC) y G3 = (D). Los grupos iniciales de ? = { (E), (ABCD) } han sido analizados, por lo tanto debemos seguir con la etapa (3) del algoritmo de partición. Paso 3. con ? : Comparamos?nueva { (E) , (ABC) , (D) } = { (E), (ABCD) } ? LyA ¡ No son iguales ! Por lo tanto el paso (3) dice que debemos repetir la etapa (2), pero ahora con : ? = ?nueva Bueno, aplicaremos de nuevo la etapa (2). Trataremos de encontrar mas particiones.
158 Transiciones para a Transiciones para b A B C B B B A B C C D C Entonces, la partición de (ABC) es : (AC) y (B). Estos nuevos subgrupos son añadidos a ?nueva, en lugar del grupo (ABC) : ?nueva = { (E), (AC), (B), (D) } Enseguida probamos el paso (3) y vemos que : ? ? ?nueva Por lo tanto, repetimos el paso (2), con ? := ?nueva. ? = {(E), (AC), (B), (D)} es el
valor para la partición que se somete al paso (2). El único grupo que puede particionarse es (AC). Analicemos pues, sus transiciones : Transiciones para a Transiciones para b A C B B A C C C a a a b b a a b b b En las transiciones para a , todos van a un estado de este grupo. Por lo tanto no hay partición. En las transiciones para el símbolo b , el estado B transiciona a un estado D que no pertenece a este grupo. Por lo tanto si hay partición. Los estados A y C tienen transición hacia un estado B que no pertenece a su grupo.Si hacemos la partición, A y C quedarían en un mismo grupo ya que los dos transicionan al mismo estado B. Por lo tantoel grupo queda igual (AC). O sea que : ?nueva = ? , por lo tanto nos vamos al paso 4. Los dos estados A y C, transicionan a un estado C que está dentro de su mismo grupo. NO HAY PARTICIÓN
159 A B a b b LyA a LyA Lo que queda por realizar es obtener la tabla de transición del nuevo AFD mínimo. Los renglones de dicha tabla serán los estados representativos. Las transiciones son obtenidas del autómata 3.11.1. Símbolos en la entrada Estados representativo s Observa que respecto a la tabla 3.11.2 , el estado C es sustituído por el estado A. El estado C ya no existe como renglón en la nueva tabla de transición del AFD reducido. Y el AFD mínimo o reducido es el que se
muestra a continuación : E En el paso (4), de ? = {(E), (AC), (B), (D)} seleccionamos de cada grupo, un estado representativo. Es claro, que los estados representativos para los grupos (E), (B) y (D) son los mismos estados que componen a cada grupo. Pero en el grupo (AC) si debemos escoger a uno de los estados sea A, o bien C, como un estado representativo. Yo selecciono al estado A como representativo del grupo (AC) !!
160 reconoce la expresión regular: Id ? (Letra) (Letra|Dig|Sub)* Dándole un vistazo al AFD 3.9.1, vemos que el conjunto de estados S es : S = {A, B, C, D, E} donde A es el estado de inicio s0 , y F = {B, C, D, E} es el conjunto de estados de aceptación. Aplicando el paso (1) del algoritmo de partición, tenemos la partición inicial ? es : (A) (BCDE) Entonces, // Estados de no aceptación S-F // Estados de aceptación F ? = { (A) , (BCDE) }. El procedimiento del paso (2) nos dice como calcular la nueva partición ?nueva. Observemos las transiciones de los estados del grupo (BCDE). El grupo (A) ya no es susceptible de partición. b D a a Reducir a su óptimo el AFD 3.9.1 del ejemplo 3.9. El AFD 3.9.1 inicio b Ejemplo 3.12. LyA Continuamos con el paso (2). Obtener una nueva partición : ?nueva
161 B C C D E C C C B D C D E D D D B E C D E E E E Sub Sub Sub • Transiciones símbolo Sub Sub Dig Dig Dig • Transiciones símbolo Dig Dig Letra Letra Letra • Transiciones símbolo Letra Letra Todos los estados transicionan a un estado C, y éste pertenece al mismo grupo. Por lo tanto : No hay partición. Todos los estados transicionan a un estado D, y éste pertenece al mismo grupo. No hay partición. Todos los estados transicionan a un estado E, y también como sucedió en los anteriores 2 casos, E pertenece al mismo grupo. Por lo tanto : No hay partición. Entonces, LyA Efectivamente en esta etapa no hubo partición, lo que quiere decir que : ?nueva = ? = { (A) , (BCDE) }
162 Dig Letra A inicio B Al aplicar el paso (3) la igualdad ?nueva = ? se cumple, por lo que la secuencia del algoritmo nos envía al paso (4), con ?final = ?. Paso 4. Seleccionar los estados representativos de cada grupo de ?final . LyA Selecciono del grupo (A) al propio A , y de ( BCDE ) a B. Construimos la tabla de transición del nuevo AFD reducido, donde los renglones son los estados representativos. Símbolos en la entrada Estados Representativos El diagrama del AFD mínimo, ahora se ha reducido de 5 estados a 2, y los arcos que antes eran 13 ahora sólo son 4, tal y como es mostrado enseguida. Letra Sub AFD mínimo para : Id ? (Letra) (Letra|Dig|Sub)* Ejemplo 3.13. Construir el AFD reducido o mínimo, a partir del AFD 3.10.2 del ejemplo 3.10, (pag. 156).
163 Haciendo referencia al AFD 3.10.2 encontramos que : S = {A, B, C, D, E, F} Del algoritmo de partición, el paso (1) es encontrar la partición inicial ? : (ABCDE) (F) // Estados de no aceptación, S-F // Estados de aceptación, F A B B B C // No tiene transición. Se agrega un “estado muerto” Z; C Z D E E E • Transiciones símbolo Vocal A Z LyA De lo anterior, ? = { (ABCDE) , (F) }. Ya tenemos la partición inicial, ahora debemos proceder a encontrar una nueva partición ?nueva . Paso 2. El grupo (F) ya no tiene mas partición. Analicemos el grupo (ABCDE) para cada símbolo en la entrada. Existen 4 posibles entradas : Cons, Vocal, Tres, Otros; según el ejemplo 3.10. (ver tabla de transición de dicho ejemplo). • Transición símbolo Cons C transiciona a un estado Z que no se encuentra en el grupo (ABCDE). Por lo tanto hay partición.(ABDE) y (C)
164 B C D E Z D E E • Transiciones símbolo Tres // Ya está hecha la partición // Los estados D y E tienen transición a un estado F, que no existe en el grupo. La partición ya está hecha. A B C D E C C Z F F • Transiciones símbolo Otros A B C D E Z Z Z F F Al probar la condición en el paso (3) encontramos que : ?nueva ? ? Por lo que tenemos que repetir el paso (2), según el algoritmo de partición. Ya que no existe transición, debemos mandar los estados A y B a un estado muerto Z. La partición existe y ahora será formada por los grupos(AB) (DE) (C) Los estados A, B y C transicionan a un estado muerto Z y D,E transicionan a un estado F. Tanto Z y F no pertenecen al grupo, por lo que la partición nueva es : ?nueva = { (AB) , (C) , (DE) , (F) }
165 Ahora, ? := ?nueva = { (AB) (C) (DE) (F)}. Analicemos los grupos (AB) y (DE), ya que (F) y (C) no tienen partición posible. • Grupo (AB) Observamos que A y B siempre transicionan a un mismo estado ya sea B o Z; por lo tanto no hay partición. • Grupo (DE) Grupo (AB) Estado representativo A LyA ¡¡ Puff !! Pues de nuevo, vayamos alpaso (2). LyA Lo mismo observamos para los estados D y E. Siempre la transición es hacia un mismo estado, sea E o bien F. No hay partición Asi que al probar la condición en el paso (3) encontramos que : ?nueva = ? Ahora si !! , pasaremos al paso (4) a seleccionar los estados representativos. Paso (4).
166 (C) (DE) (F) C D F La tabla de transición del nuevo AFD mínimo es : Símbolos en la entrada Estados Representativos y el autómata AFD construido a partir de la anterior tabla, es el resultado buscado. Sabemos que Letra ? Cons | Vocal; y que Dig ? Tres | Otros. Aplicamos estas definiciones al AFD y tenemos al nuevo diagrama del AFD mínimo o reducido : 3.7 PROPIEDADES DE LOS LENGUAJES ACEPTADOS POR UN AUTÓMATA FINITO. Otros Cons Cons Vocal D C F inicio Tres Vocal A Tres Dig Cons Letra D C F inicio Tres Vocal A
? = {x 167 Generalmente, un
lenguaje regular es un subconjunto de la cerradura de un alfabeto, esto es : L(r) ? ? * ( 3.6.1 ) ?1 = {x | | x | = 1} // Cadenas de longitud 1 2 ?3 = {x | | | x | = 2} | x | = 3} // // Cadenas de longitud 2 Cadenas de longitud 3 Por definición una expresión regular denota un lenguaje regular (conjunto de cadenas), cuyas cadenas son una concatenación de símbolos de un alfabeto ?. Y dado que la cerradura se define como : 8 ? * = U ? = ?0 U ?1 U ?2 U ?3 U … i=0 donde : ?0 = {?} Podemos ver que si L(r) ? ? *, entonces un lenguaje regular, puede ser aquél que sólo tenga la cadena vacía ?. El autómata que reconoce a este lenguaje regular es : inicio El estado de inicio también es un estado de aceptación. 1 cadenas que lo componen puedan ser reconocidas por un autómata finito. LyA En el capitulo 1 sección 1.5, se estableció que una expresión regular denota a un lenguaje regular. ¿ Qué quiere decir lo anterior ? Estamos ciertos, que una expresión regular se define sobre un alfabeto donde, el alfabeto ? es un conjunto finito de símbolos. Entonces un lenguaje regular es un conjunto de cadenas formados a partir de los símbolos de ?. Un autómata finito es un reconocedor de cadenas, especificadas por una expresión regular. Por lo tanto, un autómata finito es un reconocedor de un lenguaje regular. Un autómata finito reconoce solamente : Lenguajes regulares .
168 3.8 DETERMINACION DE LENGUAJES REGULARES Y NO REGULARES. Algunos lenguajes no pueden ser descritos por una expresión regular. Las
expresiones regulares no pueden ser usadas para describir construcciones anidadas o balanceadas. Por ejemplo, el conjunto de los paréntesis debidamente balanceados, no puede ser denotado por una expresión regular. La repetición de cadenas es otro ejemplo de un lenguaje que no puede ser denotado por una expresión regular. Por ejemplo, sea L = {wcw | w es una cadena de a’s y b’s}. Algunos lexemas de este lenguaje : aabcaab, aca, bcb, aaabbcaaabb, … etc. El autómata finito debe reconocer una cadena w luego esperar por un símbolo c, para luego esperar la misma cadena que entró antes de la c. ¿Como guarda el autómata finito esa
información para luego que c sea reconocido, esperar la misma cadena? NO PUEDE HACERLO. El autómata finito no puede, no tiene elementos para almacenar información de la entrada. Otros ejemplo es el lenguaje L = { xnyn | n = 0 }. Obtengamos los AFD’s para diferentes
valores de n : Conforme n sea un número entero lo suficientemente grande, el número de estados también se eleva en proporción 2*n, tendríamos un autómata no programable debido al elevado número de estados que lo forman, cuando n es un número arbitrariamente grande.
169 3.9 EJERCICIOS PROPUESTOS. 1. Encontrar los componentes S, s0 , F, ? y la tabla de transición, para los siguientes autómatas : (a ) (b) inicio c a b a b ? ? ? 0 1 2 3 4 LyA Lenguajes como los anteriores, que no pueden ser reconocidos por un autómata finito, se denominan lenguajes no regulares. Si existe un autómata finito que reconozca a las cadenas de un lenguaje, éste es un lenguaje regular ; de lo contrario es un lenguaje no regular. 4 3 2 1 0 + + – – inicio
170 (c) (d) 2. ¿ Cuáles de los autómatas en el ejercicio 1, son determinísticos y cuáles no determinísticos ? . 3. Aplica el algoritmo de la Fig. 3.5 para el siguiente AFD y cadenas de entrada : (a) != inicio Dig Dig c|f |d % 0 1 2 4 3 Dig +|- inicio Dig 2 | 4 | 6| 8 . 0 1 3 2 3|5|7 0|1|9 2|4
171 (b) < (c) = = 4. Aplica el algoritmo de
simulación para el AFD que se muestra y las siguientes cadenas de entrada : (a) 7651.27 (b) 3.8 (c) 4769.486 0 ! = 4 3 2 1 = = inicio 8 7 6 5 = = < > Dig Par Non Non . Par inicio 0 1 2 3 5. Aplica el algoritmo de Thompson para construir los AFND’s que reconozcan las expresiones regulares : Par (b) ( w + x ? ) ( y ? | z* ) ?
172 (c) ( a | b + ) ? ( c* d ? ) * (d) <= | < | > | >= | = = | != (e) ( 0 | 2 | 4 ) ? ( a | b* ) + (f) ( Dig* ) ( Non ) ( Punto ) ( Par ) ( Dig* ) // Punto . (g) ( Letra* ) ( Dig* ) ( 2 ) ( 1 ) 6. Obtener los AFD’s correspondientes a los ejercicios 5 a) hasta 5 g). Utiliza el algoritmo de construcción de subgrupos. 7. Minimiza los AFD’s encontrados en el ejercicio 6, utilizando el algoritmo de minimización por particiones sucesivas.
