Practico

Teoría de la Computación y Sistemas Formales 2
Práctico 1 – Conjuntos y Lenguajes

Ejercicios Mínimos

1) Repaso de conjuntos. Demostrar las siguientes propiedades:
a. A  A  B
b. A  B  Ac. A – B = A  Bc
d. A  (B  C) = (A  B)  (A  C)
e. A  A = A y A  A = A
f.

(idempotencia de unión e intersección)

(Ac)c = A

(involución del complemento)

g. (A  B) = A  B y (A B) = A  B
c

c

c

c

c

c

(Leyes de De Morgan)

2) Repaso de inducción completa. Demostrar las siguientes ecuaciones:
a. n  N : 1  4  ...  n 2 

n(n  1)(2n  1)
6

b. n N : 1  8  ...  n 3 

n 2 (n  1) 2
4

3) Plantear una representación de conjuntos en python mediante listas. Escribir las funciones
pertenece, incluye, union, interseccion, esIgual,diferencia, productoCartesiano, esVacio
para dicha representación.
4) Escribir la función potencia que, dado un conjunto, retorne el conjunto potencia del mismo.
Ejemplo: pot([1,2,3]) = [[ ], [1], [2],[3], [1,2], [1,3], [2,3], [1,2,3]].

5) Dados los lenguajes K, L y M definidos sobre el vocabulario V = {a, b}
K = {, a, aab}

L = { w / w = a2n, n > 0}

M = { w / w = an, n > 0}  {w / w =anbn, n > 0}

Calcular K o K, K o L, K*, L  M, (L  M)*, L*.
6) Siendo V un alfabeto cualquiera, probar las siguientes propiedades para lenguajes A, B, C  V*:
a. A o (B o C) = (A o B) o C
b. A o{} = {} o A = A
c. A o (B  C) = (A o B)  (B o C)
d. (A  B)* = (A*  B*)*

7) Tomando la definición de concatenación vista en clase:

Teoría de la Computación y Sistemas Formales 2Práctico 1 – Conjuntos y Lenguajes
elemento º cadena
a. Utilizar esta definición para extenderla a:
cadena º cadena
b. Utilizando la definición obtenida de la parte a, implementar una función en pythonque dadas
dos cadenas devuelva la concatenación de las mismas.

Ejercicios Complementarios

8) Siendo V un alfabeto cualquiera, ¿cuáles de las siguientes propiedades son válidas para
lenguajes...