Práctica 0: Preliminares (Teoría de Lenguajes)

Ejercicio 01

• Σ^0 = {λ}
• Σ^1 = {a,b}
• Σ^2 = {aa,ab,ba,bb}
• Σ* = {λ,a,b,aa,ab,ba,bb,..}
• Σ+ = {a,b,aa,ab,ba,bb,..}
• |Σ^1| = 2
• |Σ^0| = 1

Ejercicio 02

• x^0 = λ
• x^1 = abb
• x^2 = abbabb
• x^3 = abbabbabb
• П{k=0..3} x^k = λ.x.xx.xxx = x^(3!)
• x^r = bba

Ejercicio 03

Valen: λ $\in$ Σ*, Σ^0 = {λ}

Ejercicio 04

• xy = abbacb
• (xy)^r = bcabba
• y^r = bca
• y^r.x^r = (xy)^r
• λx = x
• λy = y
• xλy = xy
• x^2.λ^3.y^2 = abbabbacbacb

Ejercicio 05

• Σ $\cup$ A = {a,b,c}
• Σ $\cap$ A = {a}
• Σ.A = {a,b}.{a,c} = {aa,ac,ba,bc}
• Σ.A+ = {a,b}.{a,c,ac,aa,cc,..} = {a.a,a.c,a.ac,a.aa,a.cc,.., b.a,b.c,b.ac,b.aa,b.cc,..}
• Σ+.A = {a,b,ab,aa,bb,..}.{a,c} = {a.a,a.c, b.a,b.c, ab.a,ab.c, aa.a,aa.c, bb.a,bb.c,..}
• (Σ.A)+ = {aa,ac,ba,bc}+ = {aa,ac,ba,bc,aa.aa,aa.ac,aa.ba,aa.bc,ac.aa,..}
• (Σ.A)* = {aa,ac,ba,bc}* = {λ,aa,ac,ba,bc,aa.aa,aa.ac,aa.ba,aa.bc,ac.aa,..}
• Σ*.A* = {λ,a,b,ab,aa,bb,..}.{λ,a,c,ac,aa,cc,..}
• Σ.Λ.A = Σ.A

Ejercicio 06

a) V, b) F, c) V, d) V, e) F, f) V, g) V, h) V

Ejercicio 07

• a) {λ,ab,aabb,aaabbb,..}
• b) {ab,aabb,aaabbb,..}
• c) {b,ab,aab,aabb,..}
• d) {a,aa,aab,aabb,..}
• e) {acbabbab,aacacbabbabbabbab,...}
• f) {λ,a,b,aa,ab,..,aaa,...}
• g) {aa,bb,abba,..}
• h) {a,b,aa,bb,abba,..}

Ejercicio 08

• L1 = {a^k.b^k | k>=1}
• L2 = {a^(2k).b^k | k>=1}
• L3 = {a^k.b.c^k | k>=3}