Teoria de la Computación (CCOMP4-1)
Periodo: 2022.1
Programa: Ciencia de la Computación
Prof. Marcela Quispe Cruz
Fecha de Entrega: 2 de mayo del 2022
INSTRUCCIONES: Las soluciones de los ejercicios deberán ser hechas a mano en papel (con lapicero
negro o azul) o algún dispositivo como un tablet (¡esfuercese en la letra!), escaneado (si se hace en papel)
en un solo archivo PDF. También tiene la opción de entregar los ejercicios en fı́sico en la secretarı́a de la
sala de profesores del edificio Newman el mismo dı́a 2 de mayo. Si algo le imposibilita hacer la lista a mano,
hábleme antes de enviar en otro formato, de lo contrario su calificación en esta lista de ejercicios será
cero. Asegúrese de que el resultado final sea legible, el texto debe estar siempre en el sentido horizontal
de la página. ¡No entregue su primera solución! Pase a limpio antes.
Busque atendimiento conmigo siempre que tenga preguntas sobre los ejercicios.
Lista de Ejercicios 01
1. Formalice la descripción de las máquinas M1 y M2 a continuación y muestre las tablas de computación
de las cadenas ω = abbaabaaa y α = aabaabbb sobre ambas, conforme el modelo. Concluya: ¿M1 acepta
ω? ¿ M1 acepta α? ¿M2 acepta ω? ¿M2 acepta α?
2. Describa, por medio de un diagrama, un autómata finito determinı́stico (AFD) que reconoce los len-
guajes a continuación.
(a) {ω ∈ {0, 1}∗ : ω comienza con 1 y finaliza con 0 }
(b) {ω ∈ {0, 1}∗ : ω comienza con 0 y |ω| es impar o ω comienza con 1 y |ω| es par }
(c) {ω ∈ {a, b}∗ : ω no es igual a aa y no es igual a aaa }
(d) {ω ∈ {a, b}∗ : |ω|a es impar y ω termina con un b } ( Obs.: |ω|a significa el número de a’s en ω)
(e) {ω ∈ {a, b}∗ : ω no contiene ab y ni ba como subcadenas }
(f) {ω ∈ {0, 1}∗ : ω comienza con 1 y cuando interpretada como entero en binario es múltiplo de 5 }
(g) El conjunto vacio
(h) Todas las cadenas excepto la cadena vacı́a
3. Sea M un AFD que reconoce un lenguaje L. Sea N el AFD generado a partir de M cuando se tornan los
estados finales en no finales y vice-versa. Demuestre que N reconoce el complemento de L, L̄ = Σ∗ − L.
Concluya que los lenguajes regulares son cerrados bajo complemento.
4. Formalice la descripción de las máquinas N1 y N2 a continuación y muestre las tablas de computación
de las cadenas ω = abbaab y α = babaab sobre ambas, conforme el ejemplo. Concluya: ¿N1 acepta
ω? ¿N1 acepta α? ¿N2 acepta ω? ¿N2 acepta α?
5. Describa, por medio de un diagrama, un autómata finito no determinı́stico (AFN) que reconoce los
lenguajes a continuación.
(a) {ω ∈ {0, 1}∗ : ω termina con 11} (use hasta 3 estados)
(b) {ω ∈ {0, 1}∗ : ω comienza con 0 y |ω| es impar o ω comienza con 1 y |ω| es par} (hasta 5 estados)
(c) {ω ∈ {a, b}∗ : |ω|a es par o |ω|b = 2} (hasta 6 estados)
(d) {ω ∈ {a, b}∗ : al menos una de las 4 últimas posiciones de ω es b }
(e) {ω ∈ {a, b}∗ : la longitud de ω es impar pero no múltiplo de tres }
(f) {ω ∈ {0, 1}∗ : w contiene un número par de 0s, o contiene exactamente dos 1s }, un AFN con 6
estados
(g) {0x 1y 0z : x ≥ 0, y ≥ 0, z ≥ 1}
6. Convierta los AFNs N3 , N4 y N5 a continuación en AFDs usando el método de conversión visto en
clase (Teorema 1.39 del libro de Sipser):
7. Construya AFDs para los siguientes lenguajes:
(a) L1 = {ω ∈ {a, b}∗ : ω tiene un número par de a’s }
(b) L2 = {ω ∈ {a, b}∗ : cada a es seguida de por lo menos una b }
(c) L3 = {ω ∈ {a, b}∗ : ω tiene tamaño par }
(d) L4 = {ω ∈ {a, b}∗ : ω tiene un número impar de a’s }
(e) L5 = {ω ∈ {a, b}∗ : ω contiene la subcadena baba }
(f) L6 = {ω ∈ {a, b}∗ : ω = aa o aaa }
8. Utilizando los AFD construidos en el ejercicio anterior y las propiedades de clausura de los lenguajes
regulares, cree AFDs o AFNs para los siguientes lenguajes (no cree autómatas para los lenguajes
directamente):
(a) R2 = L3
(b) R3 = L3 ∪ L4
(c) R4 = L3 .L∗1
9. Convertir el AFN de la pregunta anterior parte b en una expresión regular equivalente. Muestre los
pasos de la conversión.
Page 2
10. Sea X el lenguaje {an bm al bl am bn |n, m, l ≥ 0}
(a) Demostrar que X no es regular.
(b) Demostrar que X es libre de contexto.
11. Diseñe gramáticas para cada lenguaje abajo.
(a) L1 : {ai b | i ≥ 1}
(b) L2 : {(ab)i a | i ≥ 0}
(c) L3 : {ai b | i ≥ 2}
(d) L4 : {ai baj | i ≥ 1, j ≥ 0}
(e) L5 : {ai b | i ≥ 0}
(f) L6 : {ai bj | i ≥ 0, j > 0}
(g) L7 : {(ab)i | i ≥ 0}
12. Para cada lenguaje abajo, determine una gramática que la genere. Cuando no especificado, w es un
string sobre el alfabeto Σ = {a, b}
(a) L = {w | w posee la misma cantidad de ocurrencias de a’s y de b’s }
(b) L = {w | el tamaño de w es impar y el sı́mbolo del medio es a}
(c) L = {w | w posee, máximo, 2 ocurrencias de a}
(d) L = {an bm cm dn | n ≥ 0 e m > 0}
(e) L = {an bm | 0 ≤ n ≤ m ≤ 2n}
(f) L = {wcx | wR es sufijo de x, x ∈ {a, b}}
(g) L = {ai bj ck | k = i + j}
(h) L = {an bn+m cm | n, m ≥ 0}
13. Presente autómatas de pila que acepten los lenguajes de las partes (f), (g) y (h) de la pregunta anterior.
14. Sea la siguiente gramática libre de contexto:
S → A1 A2 |B
A1 → 0A1 1|ϵ
A2 → 2A2 3|ϵ
B → 0B3|C
C → 1C2|ϵ
(a) ¿Qué lenguaje genera esa gramática ?
(b) ¿Esa gramática es ambı́gua? En caso afirmativo, justifique su respuesta usando árbol de análisis
sintáctico
Page 3