jueves, 26 de febrero de 2009

Ejercicios de Teoria de la computación

Ejercicios de Teoría de la Computación


1. Expresar en extensión el conjunto {x x Є N, x <>
2. Expresar en intención el conjunto {4, 6, 8, 12, 14, 16}.
3. ¿Cuál es el tamaño del conjunto {Ø} (esto es, cuántos elementos contiene)?
4. Sean los conjuntos A = {a, b}, B = {1, 2, 3}. Calcular las siguientes operaciones:
a) (A U B) - A
b) A U (B - A)
c) 2 A U B
d) A × (A ? B)
5. Calcular los conjuntos potencia de los siguientes conjuntos:
a) {a, b, c}
b) {a, {b, c}}
c) {Ø}
d) {Ø, {Ø}}
6. Sea el conjunto A = {a, b, c}. Proponer:
a) Una relación en A × A
b) Una función en A → A
c) Una relación en A × A que no sea función.
7. Proponer las características, en términos de reflexividad, simetría y transitividad, que debe tener la relación “x es padre de y” (se entiende que “padre” incluye también a “madre”).
8. Un juego infantil consiste en proponer simultáneamente ya sea “piedra”, “tijeras” o “papel”. Se supone que tijera gana sobre papel, piedra sobre tijera, y papel sobre piedra. Determinar si la relación “gana sobre”, que es un subconjunto de {piedra, tijeras, papel} × {piedra, tijeras, papel} es:
a) Reflexiva
b) Simétrica
c) Transitiva
9. Considérese la relación {(a, d), (b, d), (c, a), (d, d), (c, b)}. Calcular su cerradura:
a) Reflexiva
b) Simétrica
c) Transitiva
d) Reflexiva y transitiva
e) Transitiva y simétrica
f ) Reflexiva, transitiva y simétrica (estas son llamadas “relaciones de equivalencia”.

10. Considérese la relación {(a, d), (b, d), (d, d), (c, b)}, siendo el dominio y el codominio el conjunto {a, b, c, d}. Indicar si esta relación es:
a) Una función
b) Función total
c) Función inyectiva
d) Función sobreyectiva
11. Considérese la función madre(x), que obtiene la madre (biológica) de cada persona.
Indica para esta función:
a) Cuáles son el dominio y el codominio
b) Si es una función total
c) Si es una función inyectiva, sobreyectiva o biyectiva

12. Considera el conjunto de números naturales tales que si son mayores que 5 o bien terminan en 5, entonces contienen algún 1 o 2.
a) Propon 3 números que cumplan la condición y 3 que no la cumplan.
b) Expresa el enunciado como una fórmula proposicional, donde M significa “mayores que 5”, T es “terminan en 5”, U es “contienen algún 1” y D es “contienen algún 2”.
c) Transforma la fórmula del inciso anterior de manera que no tenga una implicación, y aplica una ley de De Morgan al resultado.
13. Dar tres ejemplos de lenguajes basados en el alfabeto {a,b,c}.

14. Explicar la diferencia -si la hay- entre un lenguaje vacío y uno que contiene sólo la palabra vacía (tomar en cuenta que dos lenguajes son distintos sólamente cuando uno de ellos contiene una palabra que el otro no contiene).

15. ¿La palabra vacía es elemento de cualquier alfabeto? ¿Puede la palabra vacía ε formar parte de un alfabeto? ¿Puede un alfabeto contener palabras?

16. Calcular la concatenación del lenguaje {ε, aba} con {a, bb, ε}.

17. Obtener {a, bb}* (dar los primeros 10 elementos).

18. Mostrar 3 elementos de 2{a,b}* .
19. Probar que la resta de conjuntos no es conmutativa ni asociativa.
20. Probar que la intersección de conjuntos es asociativa y también conmutativa.
21. Probar que la concatenación de lenguajes es asociativa pero no conmutativa.
22. Probar que el conjunto N × N = {(1, 1), (2, 1), (1, 2), (1, 3), (2, 2), (3, 1), (4, 1), . . .} es
contable.
23. Probar que el conjunto Σ* es infinito contable.
24. Probar por inducción la propiedad de los naturales 1 + 2 + 3 + . . . + n = , para todo n ЄN.