AGL_Taller_2

Taller 2: Ponderaci´
on 10 % de la nota total de la materia. Marcar clara y completamente esta hoja y entregarla tambi´en.
Nombre completo. N´
umero dedocumento y firma 1:
Nombre completo. N´
umero de documento y firma 2:
Nombre completo. N´
umero de documento y firma 3:
Resolver en hojas blancasescritas por un s´
olo lado y numeradas, ejemplo si son 4 hojas deben estar numeradas as´ı: 1/4,
2/4, 3/4 y 4/4.
Recuerden que este taller mas que unaherramienta evaluativa, es una herramienta pedag´ogica para detectar dificultades
y superarlas a tiempo con la ayuda de compa˜
neros y el acompa˜
namientodel profesor, entonces la invitaci´on es hacer el
ejercicio a conciencia y as´ı preparar´
an muy bien evaluaciones venideras.
Para los puntos 1 al 4, debeempezar con la siguiente expresi´on regular, y llegar a la misma expresi´on regular despu´es de
aplicar las transformaciones pedidas, o a unaequivalente a la inicial.
La expresi´
on regular dada es: x(x ∪ y ∪ z)∗ ∪ x(x ∪ y)∗ x
1 Transformaci´
on de ER a AFN-con transiciones nulas:
2 Transformaci´
onde AFN-con transiciones nulas a AFN:
3 Transformaci´
on de AFN a AFD:
4 Transformaci´
on de AFN a ER:
5 Lema de bombeo: Use el lema de bombeo parademostrar que el lenguaje dado no es regular.
L = {1i 001i 00 : i ≥ 0}
6 Gram´
aticas libres de contexto: Dise˜
nar una gram´atica libre de contexto quegenere el siguiente lenguaje. Mostrar un
ejemplo de cadena de al menos 6 s´ımbolos, mostrar una derivaci´on:
L = {aaabi aaabi ∪ bbbai bbbai , i ≥ 0}

1