Problemas sobre autómatas y expresiones

regulares
Elvira Mayordomo, Universidad de Zaragoza
24 de octubre de 2014

1. Construir AFDs equivalentes a las siguientes expresiones regulares

1. a∗ ba∗ ab∗
2. b((aab∗ + a4 )b)∗ a
3. (a + b)∗ + (aba)+
4. ab(((ba)∗ + bbb)∗ + a)∗ b.
2. Construir expresiones regulares equivalentes a los siguientes AFDs:

a a
0 1 b A B
a b

b a b a a
b

a
3 2 D C
b

b a, b
2.a y 2.b

1
 b

a
a a
0 1 3 0 2
a, b
b b a b

2 1

a, b b

2.c y 2.d

3. Construir expresiones regulares equivalentes a los AFDs de los ejercicios 4

y 6 de los problemas sobre autómatas finitos (hoja del 3 de octubre de
2014).
4. Construir un AFD equivalente a la espresión regular

(00 + (1 + 01)(11 + 0)∗ 10)∗

y obtener una expresión regular equivalente a partir del autómata (utili-

zando el lema de Arden).
5. Dar una expresión regular equivalente al autómata
0 0

1 0

1 1

y comprobar que es equivalente a (11 + 10 + 0)∗ 100∗ .

6. Sea r la expresión regular sobre Σ = {a, b, c}

c∗ (ǫ + a(a + b + c)∗ + (a + b + c)∗ b)c∗

¿Es L(r) = {a, b, c}∗? ¿Es L(r · r) = {a, b, c}∗?

7. Demostrar que si L es un lenguaje regular entonces el reverso LR también
es regular.
8. Convertir el siguiente AFnD en una expresión regular equivalente.

2
 a
1 3 b

b
a b

9. Dar AFnD’s que acepten los siguientes lenguajes:

1. (6.g, 3-10-2014) El conjunto de todas las cadenas sobre {a, b} tales
que el quinto sı́mbolo empezando por la derecha es una b.
2. (6.h, 3-10-2014) Las cadenas sobre {a, b} que tienen algún par de
as separadas por una cadena de longitud 4i, con i ≥ 0.
3. {w | w termina con 00, w ∈ {0, 1}∗ }.
4. {w | w contiene la subcadena 0101, w ∈ {0, 1}∗ }.
5. {w ∈ {0, 1}∗ | w contiene un número par de 0s ó contiene exactamente dos 1s }.
10. Convertir cada uno de los AFnD’s del ejercicio anterior en un AFD equi-
valente.
11. (4.f, 3-10-2014) Convertir el siguiente AFnD en un AFD equivalente.
a b

a
A B
b

12. (5., 3-10-2014) Convertir el siguiente AFnD en un AFD equivalente.

a
a 1 2

a
a
0 b
b
b b
3 4

3
13. Convertir el siguiente AFnD en un AFD equivalente.
0, 1 0, 1

1 0, ǫ 0, 1
q1 q2 q3 q4

14. Convertir el siguiente AFnD en un AFD equivalente.

0, 1

1 0, 1, ǫ 0, 1, ǫ
q1 q2 q3 q4

15. Convertir el siguiente AFnD en un AFD equivalente.

2
a

1 a
ǫ
a
0 3

ǫ a
4 5
a

16. ¿Reconocen estos dos autómatas el mismo lenguaje?

a, b a
1 2 1 ǫ 2
b
a
a a, b

3 b

4
17. Construir AFD’s equivalentes a los siguientes AFnD’s.
1. M = (Q = {p, q, r, s}, {0, 1}, δ1, q0 = p, F = {s}),
δ1 0 1
p {p, q} {p}
q {r} {r}
r {s} ∅
s {s} {s}
2. M ′ = (Q = {p, q, r, s}, {0, 1}, δ2, q0 = p, F = {q, s}),
δ2 0 1
p {q, s} {q}
q {r} {q, r}
r {s} {p}
s ∅ {p}
18. Demostrar que todo AFnD es equivalente a un AFnD con un único estado
final o de aceptación.
19. Sea M = (Q, Σ, δ, q0 , F ) un Autómata Finito no Determinista (AFnD).
Decir si cada una de las dos siguientes afirmaciones es cierta, justificando
la respuesta.
1. Si F = Q entonces M acepta todas las cadenas.
2. Si F = ∅ entonces M rechaza todas las cadenas.
20. Demostrar que los siguientes lenguajes son regulares. En cada caso el alfa-
beto es Σ = {0, 1}.
1. {w | w contiene un número par de unos }
2. {w | w el penúltimo sı́mbolo de w es 0 y |w| ≥ 2 }
3. {w | w 6= ǫ y el último sı́mbolo de w aparece al menos dos veces en w }
21. Sea Σ = {a, b}. Convertir el siguiente AFnD en un AFD equivalente.
a b b a

ǫ b b
1 2 3 4
a

22. Demostrar que si L es un lenguaje regular, también es regular el lenguaje

resultante de eliminar un sı́mbolo del alfabeto de cualquier cadena de L.
Esto es, si L es regular, el lenguaje ELIM IN AR(L) definido por
ELIM IN AR(L) = {xz |∃c ∈ Σ, x, z ∈ Σ∗ con xcz ∈ L}

5
es regular.