LENGUAJES Y AUTOMATAS 1.
UNIDAD 3
INSTRUCCIONES: Realizar los siguientes ejercicios:
1. Sea M = (Q, ∑ , δ , q0, F) un AFD con Q = {q0,q1,q2}, = {a, b}, F = {q2} y la función
de transición :
a b
q0 q0 q1
q1 q2 q1
q2 q2 q0
a) Dibuja el autómata M
b) Traza los cómputos de M que procesan las palabras abaa, bbbabb, bababa
bbbaa
c) ¿Qué palabras de las procesadas en (b) son aceptadas por M?
3. Busca tres palabras aceptadas y tres palabras rechazadas por cada uno de los
siguientes autómatas mostrando el cómputo que las procesa. Determina cuáles
de ellos están totalmente especificados. ¿Sabrías cuál es el lenguaje aceptado
por cada uno de ellos?
a) a b) a
b
a b
b a
a,b
b
a
b
a,b
a,b
pág. 1
LENGUAJES Y AUTOMATAS 1. UNIDAD 3
c) a b a,b
b a
d) e) b a
b a
a b a b
b a b a
a,b a,b
f) g) a
a b b a
a a b b
b a a b a
b
b a
a
4. Construye AFDs que acepten cada uno de los siguientes lenguajes definidos
sobre el alfabeto = {a,b}:
a) L= {x * : la longitud de x es divisible por 3}
b) L= {x *: aba no es subpalabra de x }
c) L= {x * : x comienza por a y termina por ab }
d) L= {x * : x tiene un número par de a's y un número par de b's }
e) L= {x * : x tiene tres a's consecutivas }
f) L= {x * : toda aparición de la subpalabra aba en x, o bien va seguida de
bb, o está al final de la palabra }
g) L= {x * : si x empieza por a no contiene la subpalabra aa y si x empieza
por b contiene la subpalabra aa }
h) L= {x * : x tiene un número par de apariciones de la cadena ab }
i) L= {x * : ab es subpalabra de x si y sólo si ba es subpalabra de x }
j) L= {x * : x está formada por la concatenación de un número arbitrario
de cadenas de la forma yyR , con |y|=2 }
k) L= {x * : x no contiene ningún prefijo en el que la diferencia entre el
número de a's y b's sea mayor que tres (a favor de cualquiera de ellos) }
pág. 2
LENGUAJES Y AUTOMATAS 1. UNIDAD 3
Sobre AFNDs (autómatas finitos no deterministas):
7. Busca tres palabras aceptadas y tres palabras rechazadas por cada uno de los
siguientes autómatas no deterministas, mostrando todos los cómputos que las
procesan. ¿Sabrías qué lenguaje acepta cada uno de ellos?
a ) b b
a a
b b
b) b b c) a
a
b
a a b
a a
b
8. Construye AFNDs que acepten los siguientes lenguajes sobre el alfabeto
= {a,b,c}
a) L= {x * : x tiene algún par de a's separadas por una cadena de símbolos
de longitud 4*i, con i ≥ 0 }
b) L= {x * : |x| ≥ 5 y el quinto símbolo contado desde el final es a }
c) L= {x * : ni aa ni bb son subcadenas de x }
d) L= {x * : x tiene ab y ba como subcadena }
e) L= {x * : ccc es sufijo de x y en ninguna otra posición de x pueden
encontrarse dos símbolos iguales seguidos
Sobre AFNDs (autómatas finitos no deterministas) equivalente AFD y Minimizar
AFD
a) Autómata finito no determinístico que acepta el lenguaje
L = { x / x ∈ {0, 1}* y x contiene la subcadena 00 ó x contiene la subcadena 11}}
b) Realizar la equivalencia del NFDA del ejercicio 4 a un AFD
c) Del AFD derivado del problema anterior, minimizar el AFD
d) Autómata finito no determinístico que acepta el lenguaje .
L7 = { a2nb2k+1 / n ≥ 1 y k ≥ 0} ∪ {ax / x ∈ {a, b}* y x contiene la subcadena ba}.
Transformar a un AFD y minimizar
pág. 3
LENGUAJES Y AUTOMATAS 1. UNIDAD 3
Sobre ERs equivalentes a autómatas:
Construye expresiones regulares equivalentes a los siguientes AF's:
a) b b b) a,b
a
b a
b
a b
a
b
a,b
Construye autómatas finitos que reconozcan los lenguajes denotados por las
siguientes expresiones regulares:
a) a*bb*(a b)ab* b) b((aab* a4)b)*a
c) (a+b*a+b*)+ d) (((b*a)*a)*a)*a
e) (a2)*(b3)*(c4)*(a4)*(b3)*(c2)*
pág. 4
LENGUAJES Y AUTOMATAS 1. UNIDAD 3
pág. 5
