Lenguajes regulares
Teoría del Autómata
LENGUAJES REGULARES
Lenguajes sobre alfabetos
Para un alfabeto S = {a1,a2,…,an} se pueden numerar las
palabras de S* de la siguiente manera:
e
a1
a2
.
an
a1a1
a1a2
0
1
2
.
n
n+1
n+2
para S = {a, b}, podemos numerar sus cadenas con dígitos
binarios 1 y 2 en vez de 0 y 1. Sea a el 1 y b el 2, entonces se
obtiene
abaa
aa
ab
1211
e
a
b
11
12
=
0
1
2
=
=
19
3
4
de esta manera se representa cada cadena como un entero único.
Y cualquier número podemos representarlo como una secuencia
de a’s y b’s, por ejemplo el 32 se convierte a 11112 y luego a
aaaab.
Teorema 1. Para todo alfabeto S, S* es infinito enumerable.
Teorema 2. El conjunto de todos los lenguajes sobre S no es
numerable.
Demostración. Llamemos L al conjunto de todos los lenguajes
sobre S, si L es numerable, por tanto podemos enumerarlo como
A0, A1, A2, …
S* puede numerarse como w0, w1, w2, … Sea B = {wi | wi  Ai}. B
contiene las palabras que no pertenecen al lenguaje que tienen el
mismo índice que las mismas. Pero como B es un lenguaje B = Ak
para algún k. Si wk  B, entonces wk  Ak = B. Y por lo tanto wk
esta y no esta en Ak. Lo mismo sucede si suponemos wk  B. Por
lo tanto L no es numerable.
El teorema 2 estipula que hay una cantidad innumerable de
lenguajes sobre un alfabeto particular.
Por tanto, no existe ningún método de especificación de
lenguajes que sea capaz de definir todos los lenguajes sobre
un alfabeto.
Lenguajes regulares y
expresiones regulares
Sea S un alfabeto. El conjunto de los lenguajes regulares sobre
S se define recursivamente como sigue:
1.  es un lenguaje regular
2. {e} es un lenguaje regular
3. Para todo a  S {a} es un lenguaje regular
4. Si A y B son lenguajes regulares, entonces A  B, A · B ,
A* son lenguajes regulares
5. Ningún otro lenguaje sobre S es regular.
ejemplo
Por ejemplo. El lenguaje de todas las cadenas sobre {a, b, c}
que no tienen ninguna subcadena ac es un lenguaje regular, y
puede expresarse por
A = {c}* ({a}  {b}{c}*)*
Simplificación
Se puede simplificar la notación mediante el uso de
expresiones regulares. Las equivalencias son:
a  b denota {a}  {b}
ab denota {ab}
a* denota {a}*
a+ denota {a}+
Ejemplo: A = {c}* ({a}  {b}{c}*)* = c* (a  bc*)*
Expresiones regulares
Los operadores tienen precedencia (*, · , ). Entonces, una
expresión regular sobre el alfabeto S, es
1.  y e son expresiones regulares.
2. a es una expresión regular para todo a  S.
3. Si r y s son expresiones regulares, entonces r  s, r · s , r*
también lo son.
4. Ninguna otra secuencia de símbolos es una expresión
regular.
Equivalencia de expresiones
regulares
Dos expresiones regulares pueden ser equivalentes, es decir, generan el mismo
lenguaje.
La expresión (a*b)* es equivalente a e (ab)*b.
Ambos generan e o cadenas de aes y bes terminadas en b.
La expresión
ab  e (ab)*b
Es equivalente a
ab  (a*b)*
Reglas para expresiones
regulares
1.
r  s = s  r.
2.
r   = r =   r.
3.
r  r = r.
4.
(r  s)  t = r  (s  t).
5.
er = re = r.
6.
r = r = .
7.
(rs)t = r(st).
8.
r(s  t) = rs  rt y (r  s)t = rt  st.
9.
r* = r** = r*r* = (e  r)* = r*(r  e) = (r  e)r* = e  rr*.
10. (r  s)* = (r*  s*)* = (r*s*)* = (r*s)*r* = r*(sr*)* .
11. r(sr)* = (rs)*r.
12. (r*s)* = e  (r  s)*s.
13. (rs*)* = e  r(r  s)*.
14. s(r  e)*(r  e)  s = sr*.
15. rr* = r*r.
Autómata finito determinista
Podemos usar un diagrama de transición para ayudar a determinar si una
cadena pertenece o no a un lenguaje.
Los nodos del diagrama se denominan estados y se utilizan para señalar hasta
donde se ha analizado la cadena.
Las aristas se denominan transiciones y se etiquetan con los símbolos del
alfabeto.
Existe un estado, llamado estado inicial, que es de donde parte el análisis de
toda cadena.
Algunos estados se marcan como estados de aceptación para determinar si
una cadena es legal o no.
La cadena es legal si se termina su análisis en un estado de aceptación.
Los estados de aceptación se representan encerrados en un círculo.
El siguiente diagrama acepta cadenas de la forma akb.
a
a,b
b
a,b
El siguiente diagrama acepta el lenguaje A = {(ab)i | i  1}.
a,b
b
b
a
b
a
a
El siguiente diagrama
acepta cadenas de la
forma (ab)*.
El mismo autómata con estados
etiquetados q0, q1, q2
Estado/Estrada
q0
q1
q2
a
q1
q2
q2
b
q2
q0
q2
b
q0
a
b
q2
a,b
q1
a
Autómata Finito Determinista
Definimos un autómata finito determinista M como una colección de
cinco elementos:
1. Un alfabeto de entrada S.
2. Una colección finita de estados Q.
3. Un estado inicial s.
4. Una colección F de estados de aceptación o finales.
5. Una función d: Q  S  Q que determina el único estado siguiente para
el par (qi, s) correspondiente al estado actual y la entrada.
Se usará la notación M = (S, Q, s, F, d) para indicar un AFD (autómata
finito determinista) M.
Ejemplo
Por ejemplo, el AFD del diagrama anterior se representa mediante M = (S, Q,
s, F, d) donde
b
Q = {q0, q1, q2}
q0
S = {a, b}
F = {q0}
y d se define por la tabla
a
b
s = q0
q1
a
q2
a,b
d
q0
q1
q2
a
b
q1
q2
q2
q2
q0
q2
Construcción de diagramas de
transición
Para construir un diagrama de transiciones a partir de una
descripción de un autómata, se procede como sigue.
Se dibujan nodos para cada estado del autómata, luego se
trazan flechas desde cada estado qi hacia el qj etiquetándolas
con el símbolo de entrada correspondiente, se marca el estado
inicial y los estados de aceptación.
Ejercicio
Obtener la expresión regular que representa el lenguaje
formado por todas las cadenas sobre {a, b} que tienen un
número par de bes. Construir el diagrama de transición para
este lenguaje.
Ejercicio
Construir el diagrama de transición para el lenguaje dado por
c*(a  bc*)*. Convertir el diagrama en una tabla de transición
de estados.
AFD y lenguajes
Definimos el lenguaje aceptado por un AFD M como
L(M) = {w  S* | w es aceptada por M}
Por tanto, L(M) es el conjunto de las cadenas que hacen que
M pase del estado inicial a un estado de aceptación. Por
ejemplo, el siguiente AFD M = (S, Q, s, F, d) donde
Q = {q0, q1, q2, q3}
S = {a, b}
s = q0
F = {q0, q1, q2}
y d definida por la tabla
d
q0
q1
q2
q3
a
q0
q0
q0
q3
b
q1
q2
q3
q3
Tiene el siguiente diagrama de transición
a
a
b
q0
q1
b
a
a, b
q3
q2
b
acepta el lenguaje
L(M) = {w  {a, b}* | w no contiene tres bes consecutivas}
Se puede aplicar recursivamente una serie de caracteres de una
cadena dada al AFD.
Por ejemplo, la aplicación de la cadena bbab en el caso
anterior dará d(d(d(d(q0,b),b),a),b) = q1.
Esto puede abreviarse como d(q0,bbab).
Diremos que dos AFD M1 y M2 son equivalentes si L(M1) =
L(M2).
Autómata finito no determinista
Un autómata finito es no determinista si se permite que desde
un estado se realicen cero, una o más transiciones para el
mismo símbolo de entrada.
El lenguaje a*b  ab* tiene el siguiente AFD asociado.
b
q1
q0
a
a,b
a
q2
a
q3
a,b
b
q4
q5
b
q6
b
a
a,b
Consideremos ahora el siguiente diagrama de transición, este
reconoce las mismas cadena, sin embargo es mucho más
simple.
Note que el diagrama de transiciones no representa una función
de Q ´ S en Q.
a
a
q0
q1
b
a
q3
q4
b
b
q2
Definición
Definimos un autómata finito no determinista M como una
colección de cinco elementos:
1. Un alfabeto de entrada S.
2. Una colección finita de estados Q.
3. Un estado inicial s.
4. Una colección F de estados de aceptación o finales.
5. Una relación D sobre (Q  S)  Q y se llama relación
de transición.
Por ejemplo, el AFN anterior se describe por medio de
a
Q = {q0, q1, q2, q3, q4}
a
q0
F = {q2, q3, q4}
q1
b
a
s = q0
q3
S = {a, b}
q4
b
y D dada por la tabla
D
a
b
q0
{q 1, q 4}
{ q 3}
q1
{ q 1}
{ q 2}
q2


q3


q4

{ q 4}
b
q2
Por ejemplo, el AFN siguiente reconoce (ab  aba)*
b
Q = {q0, q1, q2}
q0
F = {q0}
a
a
b
s = q0
q2
S = {a, b}
y D dada por la tabla
D
q0
q1
q2
a
{q1}

{q0}
q1
b

{q0, q2}

Lenguaje aceptado por un AFN
Si M es un AFN, el lenguaje aceptado por M se define como
L(M) = {w  S* | w es aceptada por M}
Para poder decidir si una cadena no es aceptada por un AFN
deben recorrerse todas las rutas posibles en el AFN para esa
cadena, y determinar que ninguna de estas lo lleva al algún
estado de aceptación.
Ejemplo
Si X  Q, vamos a interpretar D(X, s) como el conjunto {p | q
 X y p  D(q, s)}.
Para el autómata de la figura que reconoce el lenguaje (a* b*)*
(aa  bb) (a* b*)* . OBTENER LA TABLA DE TRANSICIÓN
Para este ejemplo D({q0, q2, q3}, b) = {q0, q1}  {q2}   =
{q0, q1, q2}.
Para una secuencia de símbolos, por ejemplo abaab, se
puede escribir D(q0, abaab) = D(D(D(D(D(q0, a)b)a)a)b) =
{q0, q1, q4}.
Equivalencia de AFD y AFN
La definición de equivalencia se extiende a los AFN, es decir,
dos autómatas (AFD o AFN) M1 y M2 son equivalentes si L(M1)
= L(M2).
a,b
a,b
a
a
b
a,b
Consideremos el AFN
D(q0, a) = {q1, q2}
D(q0, b) = 
D({q1, q2}, a) = 
D({q1, q2}, b) = {q3}
D(, a) = D(, b) = 
D(q3, a) = {q2}
D(q3, b) = 
D(q2, a) = 
D(q2, b) = {q3}
AFD equivalente
{q0}
b
{q1,q2}
a
{q3}
b
a
a
b
a
b
f
a,b
{q2}
e-transiciones
Una e-transición es una transición entre dos estados que no consume
ningún símbolo.
q0
q1
a
q0
e
q1
a,e
b
a
q2
Acepta: a*
D
a
b
e
q0
{q1}
f
f
q1
f
{q2}
f
q2
{q0}
f
{q0}
e-cerradura
Si un AFN tiene e-transiciones, la relación de transición D asocia pares de
Q  (S  {e})  Q con subconjuntos de Q.
Para todo estado q  Q definimos la e-cerradura de q como
e-c(q) = {p | p es accesible desde q sin consumir nada en la entrada}
Ampliaremos esta definición para todo estado del conjunto de estados de
la siguiente manera

   e  cq 
n
e  c q i , q i , , q i
1
2
n
ik
k 1
Estados que siguen a q
Para q  Q y s  S se define
d(q, s) = {p | hay una transición de p a q etiquetada con s}
Ampliaremos esta definición para todo estado del conjunto de estados de
la siguiente manera
d
 q
   d q
n
i1
, q i2 ,  , q i n , s 
ik
,,s 
k 1
A partir de un AFN M = (S, Q, s, F, D) con e-transiciones, se puede construir
una AFN sin e-transiciones que acepte el mismo lenguaje. Se define M = (S, Q,
s, F', D') como
F' = F  {q | e-c(q)  F  }
y D(q, s) = e-c(d(e-c(q), s)).
Ejemplo: eliminación de etransiciones
q0
a
q1
e
e
b
a
e
b
q3
q2
q4
q5
e-c(q0) = {q0,q1}
d({q0, q1},a) = {q3, q4}
e-c({q3, q4}) = {q1, q3, q4, q5}
D(q0,a) = {q1, q3, q4, q5}
d({q0, q1},b) = {q2}
e-c({q2}) = {q2}
D(q0,b) = {q2}
e-c(q1) = {q1}
d ({q1},a) = {q4}
e-c({q4}) = {q4,q5}
D(q1,a) = {q4,q5}
d ({q1},b) = {q2}
e-c({q2}) = {q2}
D(q1,b) = {q2}
e-c(q2) = {q2}
d ({q2},a) = {}
e-c({}) = {}
D(q2,a) = {}
d ({q2},b) = {}
e-c({}) = {}
D(q2,b) = {}
e-c(q3) = {q1, q3}
d ({q1, q3},a) = {q4}
e-c({q4}) = {q4,q5}
D(q3,a) = {q4,q5}
d ({q1, q3},b) = {q2,,q4}
e-c({q2,,q4}) = {q2,,q4,q5}
D(q3,b) = {q2,,q4,q5}
e-c(q4) = {q4,q5}
d ({q4, q5},a) = {}
e-c({}) = {}
D(q4,a) = {}
d ({q4, q5},b) = {}
e-c({}) = {}
D(q4,b) = {}
e-c(q5) = {q5}
d ({q5},a) = {}
e-c({}) = {}
D(q5,a) = {}
d ({q5},b) = {}
e-c({}) = {}
D(q5,b) = {}
Ejemplo: eliminación de e-transiciones
D'
a
b
b
q0
{q1, q3, q4, q5}
{q2}
q1
{q4,q5}
{q2}
q2
{}
{}
q3
{q4,q5}
{q2,,q4,q5}
q4
{}
{}
q5
{}
{}
a
q1
a
a
q2
b
a
a
b
a,b
q3
q4
a,b
q5
Autómatas finitos y expresiones
regulares
Para un alfabeto S se pueden construir AFN (o AFD) que acepten palabras
unitarias y el lenguaje vacío como se muestra en la figura
q1
q2
q1
a
Sean M1 = (S1, Q1, s1, F1, D1) y M2 = (S2, Q2, s2, F2, D2) dos AFN. Podemos
unir M1 y M2 para que acepte L(M1)  L(M2), añadiendo un nuevo estado
inicial s y dos e-transiciones una de s a s1, y otra de s a s2. La construcción
formal del nuevo AFN M = (S, Q, s, F, D) esta dada por S = S1  S2, F = F1 
F2 y Q = Q1  Q2  {s}.
Autómatas finitos y expresiones
regulares
Se pueden considerar las transiciones D1 y D2 como ternas ordenadas de Q1 
S  Q1 y Q2  S  Q2, donde (q, s, p) significa que existe una transición de q a p
mediante el carácter s. De aquí
D = D1  D2  {(s, e, s1),(s, e, s2)}
Para los autómatas anteriores, se puede formar un AFN que acepte L(M1)L(M2).
Para esto, se agregan e-transiciones entre cada estado de aceptación de M1 y el
estado inicial de M2. El autómata que se obtiene es
Q = Q 1  Q2
s = s1
F = F2
D= D1  D2  {F1  {e}  {s2}}
Ds2  D(q, e) para todo q  F1
Autómatas finitos y expresiones
regulares
Es posible obtener L(M2)* de la siguiente forma. Primero se añade un estado
inicial de aceptación s’. Se agrega una e-transición de este estado a s. Se
agrega además, una e-transición entre todos los estados de aceptación y el
estado inicial s’. El autómata resultante será M' = (Q', S, s', F', D'), donde
Q = Q1  {s’}
s = s1
F = {s’}
D' = D1  {(s’, e, s)}  (F1 ´ {e} ´ {s’})
Teorema 5
El conjunto de lenguajes aceptados por un autómata finito sobre el alfabeto S
contiene  y los lenguajes unitarios {a} para todo a  S. Este conjunto es
cerrado con respecto a la unión, concatenación y la cerradura de estrella.
Consideremos un autómata finito M = (S, Q, s, F, D) y supongamos que s = q0
es el estado inicial. Para todo estado qi sea
Ai = {w  S* | D(qi, w)  F  }
Es decir, Ai es el conjunto de las cadenas sobre S que hacen que M pase
desde qi hasta un estado de aceptación. Obsérvese que A0 = L(M).
para el autómata de la figura. se tiene
A5 = , A2 = e
A4 = e,
q0
q2
q1
b
a
a
A1 = b
A3 = a, A0 = ab  ba
b
a,b
b
q5
a,b
a
q3
q4
Supongamos que qj  D(qi, s). Entonces Ai contiene a sAj. De hecho, se tiene que
Ai =  {sAj | qj  D(qi, s)}
Por ejemplo, el anterior autómata
A0 = aA1  bA2,
A3 = aA4  bA5
A1 = bA2  aA5,
A4 = e  aA5  bA5
A2 = e  aA5  bA5,
Sustituyendo se obtiene que L(M) = ab  ba.
A5 = 
Lema de Arden
Una ecuación de la forma X = AX  B, donde e  A, tiene una solución
única X = A*B.
Demostración. A*B = (A  e)B = A+B  B = A(A*B)  B, entonces A*B es
solución.
Sea X = A*B  C solución donde C  A*B  . Sustituyendo
A*B  C = A(A*B  C)  B
= A+B  AC  B
= A+B  B  AC
= (A+  e)B  AC
= A*B  AC
Realizando la intersección con C en ambos lados nos da C = AC  C. Por
tanto C  AC. Pero e  A, por tanto la cadena más corta de AC debe ser
más larga que la cadena más corta de C. Esto solo se cumple si C = .
Por tanto A*B es la única solución.
Lema 2. Sea M un autómata finito. Entonces existe una expresión regular r
para la cual L(r) = L(M).
Teorema 6 (Teorema de Kleene). Un lenguaje es regular si y sólo si es
aceptado por un autómata finito.
Ejemplo
b
q0
a
q1
a
q3
q2
a
q4
b
a
b
A4 = b*
A0 = aA1
A1 = aA2  bA4
A2 = aA3  bA4
A3 = e  aA3  bA4
A3 = aA2  b+  e
= a*b*
A2 = a+b*  bb*
A1 = a(a+b*  b+) b+
= aa+b*  ab+ b+
A0 = a2a+b*  a2b+ ab+
b
Propiedades de los lenguajes
regulares
Sea un AFD M = (S, Q, s, F, d), donde Q contiene n estados. Si L(M) es infinito,
podemos encontrar w = a1, a2, …, an+1, que pertenezca a L(M). Si
q1 = d(s, a1)
q2 = d(q1, a2)
y así sucesivamente, obtendríamos los n+1 estados, q1, q2, …, qn+1 .
Como Q tiene n estados, los qi no serán todos distintos. Para algunos índices j y k, con 1 
j < k  n+1, se tendrá que qj = qk. Por lo tanto, habrá un ciclo para llegar al estado de
aceptación. Como se muestra en la figura
q0
qj+1
q1
qj = qk
qk+1
qn+1
El lazo tiene longitud de al menos 1. Las cadenas w = a1, a2, …, aj, (aj+1,…, ak)m
ak+1,…, an+1 estarán en L(M) para m  0.
Lema del bombeo
Sea L un lenguaje regular infinito. Entonces hay una constante n de forma que, si
w es una cadena de L cuya longitud es mayor o igual a n, se tiene que w = uvx,
siendo uvix  L para todo i  0, con | v |  1 y | ux |  n.
Este lema es utilizado para probar si un lenguaje es o no regular.
Ejemplo: sea
2
L  { a i  1}
i
Toda cadena de L debe tener una longitud que sea un cuadrado perfecto.
Supongamos que cumple el lema del bombeo, entonces
a
n
2
 uvx
Se cumple que n2 = |uvx| < |uv2x| <= n2 + n < (n+1)2
Es decir, |uv2x| se encuentra entre dos cuadrados perfectos consecutivos y por tanto
no es un cuadrado perfecto. En consecuencia no pertenece al lenguaje L.
Otro ejemplo
Sea el lenguaje L = {ambm | m>=0}. L es infinito.
Si se cumple el lema del bombeo se tiene que anbn= |uvx| con | v |  1 y | ux |  n.
Dado que | ux |  n, | v | < n, y por tanto consta solo de aes. Entonces v = as, para s>=1.
Si u = ar, x = an–(s + r)bn.
Por lo tanto |uv2x| = ara2san–(s + r)bn = an + sbn.
Dado que s>=1, la cadena no puede pertenecer a L.
Teorema 7
Sea M un autómata finito de k estados.
1. L(M)   si y solo si M acepta una cadena de longitud menor que k.
2. L(M) es infinito si y solo si M acepta una cadena de longitud n, donde k  n  2k.
Demostración.
1. Si M acepta una cadena de longitud menor que k, entonces L(M)  . Si L(M) 
, entonces existe w  L(M). Supongamos | w |  k. Por el lema del bombeo w =
uvx, y uvix  L(M). En particular, ux  L(M). Si | ux |  k, quedaría probado, el
proceso se puede repetir para esta cadena hasta llegar a una longitud  k.
2. Supongamos w  L(M) con k  | w |  2k. Pero por el lema del bombeo w = uvx, y
uvix  L(M), para todo i, con lo que L(M) es infinito. Ahora supongamos que
L(M) es infinito. Habrá cadenas con longitud  k. Supongamos | w |  2k. Pero por
el lema del bombeo w = uvx, y uvix  L(M). Entonces ux  L(M). Si | ux |  2k,
quedaría probado, si no se puede repetir el proceso hasta encontrar una cadena
que se encuentre entre k y 2k – 1.
Aplicación de las leyes de de
Morgan
Supongamos que L y K son lenguajes sobre S. De las leyes de De Morgan
(S* - L)  (S* - K) = S* - (L  K)
Por tanto
L  K = S* - (S* - (L  K))
= S* - ((S* - L)  (S* - K))
Pero el complemento de un lenguaje es regular si el lenguaje es regular, por lo tanto la
intersección de dos lenguajes será regular si ambos lenguajes son regulares. Este hecho
puede utilizarse para demostrar si un lenguaje es regular o no.
Por ejemplo, sea S = {a, b} y L = {wwI | w  S*}. Probaremos que L no es regular. Sea L1
= {anb2kan | n, k  0} no regular, y L2 = {akbnam | k, n, m  0} regular. Obsérvese que L2 
L = L1. Si L fuera regular, lo sería L1. Por tanto L no puede ser regular.
Indistinguibilidad
Sea M = (Q, S, d, q0, F) un AFD. Definimos la relación de indistinguibilidad ~ en Q
como:
q, q’  Q, q ~ q’  x,  S* (d(q, x)  F  d(q’, x))
La relación ~ es una relación de equivalencia que induce una partición en Q y vamos
a definir un autómata a partir de M, obtenido mediante la agrupación de estados
pertenecientes al mismo bloque de la partición.
Minimización
a
q0
a
q4
b
q2
b
q1
b
b
a
q3
a
q6
b
a
a
b
a
b
q5
b
q7
a
a
q6 se elimina porque no es accesible.
b
q0 B1 B1
q1 B1 B1
q2 B1 B2
La partición inicial es
q3 B2 B1
p0 = {{q0, q1, q2, q3, q5, q7},{q4}}.
q5 B1 B1
Llamamos
q7 B1 B2
B1 = {q0, q1, q2, q3, q5, q7} y B2 = {q4}.
q4 B1 B2
De tabla anterior se obtiene p1
La partición es
p1 = {{q0, q1, q5}, {q2, q7}, {q3}, {q4}}.
a
b
q0 B2 B3
q1 B2 B3
q5 B1 B1
Llamamos
q2 B1 B4
B1 = {q0, q1, q5}, B2 = {q2, q7}, B3 = {q3} y B4 = {q4}.
q7 B1 B4
q3 B4 B1
q4 B1 B2
De tabla anterior se obtiene p2
La partición es
p2 = {{q0, q1}, { q5}, {q2, q7}, {q3}, {q4}}.
a
b
q0 B2 B3
q1 B2 B3
q2 B5 B4
Llamamos
q7 B5 B4
B1 = {q0, q1}, B2 = {q2, q7}, B3 = {q3} y B4 = {q4} y B5 =
{q5}.
q3 B4 B5
Puede verse que p3 es igual a p2. Por lo tanto el AFD ya
está minimizado.
q5 B5 B1
q4 B1 B4
Diagrama de transiciones
B2
a
b
B1 B2 B3
a
B1
a
b
B4
a
B2 B5 B4
b
B3 B4 B5
B4 B1 B4
b
a
b
B5 B5 B1
B3
b
a
B5
Tarea
Minimizar
a,b
q5
q0
a
q1
a
b
a
b
b
b
b
a,b
a
q3
q6
a
q2
q4
a
b
q7
Aplicaciones de los autómatas finitos
Reconocedor de números enteros
0,1,2, ..., 9
q0
1,2, ..., 9
q1
cualquier otro
carácter
cualquier otro
carácter
q2
cualquier otro
carácter
1.
2.
3.
4.
i = 1
ok = verdadero
long = longitud(s)
si s[i] en num entonces
i = i+1
mientras i<long y ok
si s[i] en num
i = i + 1
sino
ok = falso
fin si
fin mientras
sino
ok = falso
Descargar

Lenguajes regulares