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.
 Página anterior | Volver al principio del trabajo | Página siguiente  |