CIENCIAS DE LA COMPUTACION I 2009
TRABAJO PRACTICO Nº 1
LENGUAJES
1) Sean x = cd, y = ab cadenas. Calcular
a) x1 e) xR y
b) x2 f) yR xR
0
c) x g) xRy2
d) xR h) x2 y3
2) Sean L1 = { an b2k / n≥0 y k≥n } L2 = { 0m 1n / m impar y n par, ó m par y n par }
Determine para cada una de las siguientes cadenas si ∈ o ∉ al lenguaje indicado.
a) a b4 ........ L1 e) 03 13.........L2 i) 14.……............ L2
b) a b ..........L1 f) 04 18..........L2 j) 03 16 a3 b8 ..….L1 • L2
c) ε ..........L1 g) 03 12.........L2 k) a6 b8 04...….... L1 • L2
d) a5 ..….......L1 h) 09 ........ L2 l) 1 a b4.............. L2 • L1
3) Para cada uno de los siguientes lenguajes, dé al menos 3 cadenas de distinta longitud:
a) L1 = { x / x ∈ {0, 1, 2, 3, 4, 5, 6, 7, 8, 9}* y x es un número par}
b) L2 = { an bm dn+m / n, m ≥ 0}
c) L3 = { x / x ∈ {a, b, c, d}* y x contiene la subcadena ab y x no contiene la subcadena bc}
d) L4 = { x02k+1 / x ∈ {a, b, c}* y la longitud de x es múltiplo de 4 y x termina en bb y k ≥ 0}
4) Sean A y B alfabetos, A = {a, b} y B = { a, b, c}, y L1, L2 y L3 lenguajes
L1 = { ai bj / i ≥ 1, j ≥ 1 } L2 = { bi cj / i ≥ j ≥ 1 } L3 = { ai bj ci / i ≥ 1, j ≥ 1 }
Determine si cada una de las siguientes afirmaciones es verdadera o falsa.
a) L1 es un lenguaje sobre A.
b) L2 es un lenguaje sobre A ∪ B.
c) L2 es un lenguaje sobre A ∩ B.
d) L3 es un lenguaje sobre A ∪ B.
e) L3 es un lenguaje sobre A ∩ B.
f) L1 es un lenguaje sobre A - B.
g) L1 ∪ L2 es un lenguaje sobre A.
h) L1 ∪ L2 es un lenguaje sobre A ∩ B.
i) L1 - L2 es un lenguaje sobre A.
5) En cada caso dé, si es posible, un lenguaje L (que sea no vacío) que satisfaga la condición
correspondiente:
a) L ⊂ {ab, aabb, aaabbb} para L infinito
CIENCIAS DE LA COMPUTACION I 2009
b) L ⊂ {an bn ck / k, n > 0} para L infinito.
c) L ⊂ {an bk / n > 0 y k > n} para L infinito.
d) {ak b2n cn / n, k > 0 } ⊂ L, para L lenguaje finito
e) {ak b2n cn / n, k > 0 } ⊂ L, para L lenguaje infinito
f) L ⊂ {an bn ck / k > 0 y n > k}, para L lenguaje finito
g) L ⊂ {an bn ck / k > 0 y n > k}, para L lenguaje infinito
6) Sean L1 = {ε}, L2 = {b, aa, ab, bb}, L3 = {ε, a, b, aa, bb} y L4 = ∅, definidos sobre A = {a, b}.
Obtener a) L1 ∪ L2, b) L1 ∪ L3, c) L1 ∪ L4, d) L1 ∩ L2, e) L2 ∩ L3, f) L3 ∩ L4, g) L1 ∩ L4
7) Dados los siguientes lenguajes, definidos sobre el alfabeto A = {a, b, c}
L1 = {ε, a, ab} L2 = { x / x ∈ {a, b, c}* y x termina en a}
L3 = { x / x ∈ {a, b, c}* y x termina en b}
Calcule el lenguaje resultante de las siguientes operaciones:
i) L12 ∩ L3 ii) L2 ∪ L1 iii) L1R – L2 iv) L1 ∩ L3R
8) Determine si las siguientes igualdades sobre lenguajes definidos sobre el alfabeto A = {a, b, c}
son verdaderas o falsas, justificando en cada caso. Para las falsas, dé un contraejemplo.
a) { a3i bi / i ≥ 0 } = ({a}.{a}.{a})* . {b}*
b) { a3i bn / i, n ≥ 0 } = ({a}.{a}.{a})* . {b}*
c) {w / w ∈ {a, b, c}* y w comienza con a } = ({a} ∪ {b} ∪ {c})*
d) {w / w ∈ {a, b}* y w tiene al menos dos a} = {b}*. {a} . {b}*. {a}. ({a} ∪ {b})*
e) {w / w ∈ {a, b, c}* y w no comienza con a } = ({ε} ∪ {b} ∪ {c}) . ({a} ∪ {b} ∪ {c})*
9) Sean L1 y L2 los siguientes lenguajes: L1 = { a } L2 = { b }
Determine los conjuntos de cadenas que pertenecen a los siguientes lenguajes:
a) L1*
b) ( L1 • L2 )*
c) ( L1 ∩ L2 )*
d) L1* • L2*
e) ( L1 ∪ L2 )*
10) Dados los siguientes lenguajes, definidos sobre el alfabeto A = {a, b, c, d, e, g}
L1 = {ε, ab, a} L2 = {ε, d, c} L3 = { x / x ∈ {a, b, c}* y x termina en ab}
L4 = { aj+1 bp d2n ek gs / p, k, s ≥ 0 y n > s y j > p}
Calcule el lenguaje resultante de las siguientes operaciones:
a) L12 - L3 b) L1 . L2* c) L4R d) L12 ∩ L3 e) L1 ∪ L22
11) Describa si es posible, mediante un único conjunto las siguientes operaciones:
a) { ak bn dk+n gi hs / k, n, i, s ≥ 0 y i ≥ s} ∪ { ak bn dk+n gi hs / k, n, i, s ≥ 0 y i > s}
b) { ak bn dk+n gi hs / k, n, i, s ≥ 0 y i ≥ s} ∩ { ak bn dk+n gi hs / k, n, i, s ≥ 0 y i > s}
c) { an b2k / n, k ≥ 0} ∩ {a2n+1 bk / n, k ≥ 0}
d) { an b2k / n, k ≥ 0} ∪ {a2n+1 bk / n, k ≥ 0}
e) { an b2k / n, k ≥ 0} - {a2n+1 bk / n, k ≥ 0}
