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 = x^2.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,ab,aa,aab,aabb,..}
• e) {acbabbabbab,aacacbabbabbabbab,...}
• f) {λ,aaa,aab,aba,abb,baa, ... }
• 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}

Ejercicio 09

a)
|a.(a.α)| = 1+|a.α| = 1+1+|α| = 2+|α|

b)
CB: x=λ
|λ^r| = |λ|
PI: x=a.α (vale |α^r|=|α|)
|(a.α)^r| = |α^r.a| =(Lema 1) |α^r|+|a| = |a|+|α^r| =(HI) |a|+|α| =(Lema 1) |a.α|

* Lema 1: |x.y| = |x|+|y|
CB: x=λ
|λ.y| = |y| = 0+|y| = |λ|+|y|
PI: x=a.α (vale |α.y| = |α|+|y|)
|(a.α).y| = |a.(α.y)| = 1+|α.y| =(HI) 1+|α|+|y| = |a.α|+|y|

c)
|x.x| =(Lema 1) |x|+|x| = 2|x|

d)
CB: α=λ
(λ.β)^r = β^r = β^r.λ = β^r.λ^r
PI: α=a.x ( vale (x.β)^r = β^r.x^r )
([a.x].β)^r = (a.[x.β])^r = [x.β]^r.a = (HI) β^r.x^r.a = β^r.[a.x]^r

e)
CB: α=λ
(λ^r)^r = λ^r = λ
PI: α=a.x ( vale (x^r)^r = x )
([a.x]^r)^r = (x^r.a)^r = a^r.(x^r)^r =(HI) a.x

f)
CB: n=1
(α^r)^1 = α^r
(α^1)^r = α^r
PI: n+1 ( vale (α^r)^n = (α^n)^r )
(α^r)^(n+1) = α^r.(α^r)^n =(HI) = α^r.(α^n)^r = (α^n.α)^r = (α^(n+1))^r

Ejercicio 10

• a) x en F(F(A)) <=> EX b | bx en F(A) <=> EX b | (EX c | cbx en A) <=> (α=cb) EX α | αx en A <=> x en F(A)
• b) x en S(S(A)) <=> EX b,c | bxc en S(A) <=> EX b,c | (EX d,e | dbxce en A) <=> (α=db, β=ce) EX α,β | αxβ en A <=> x en S(A)
• c)
• d) x en I(AUB) = EX b | xb en AUB = EX b | ( xb en A o xb en B) = (EX b | xb en A) o (EX b | xb en B) = x en I(A) o x en I(B) = x en I(A) U I(B)
• e) x en F(AUB) = EX b | bx en AUB = EX b | ( bx en A o bx en B) = (EX b | bx en A) o (EX b | bx en B) = x en F(A) o x en F(B) = x en F(A) U F(B)
• f)
  • x en I(S(A)) = EX b | xb en S(A) = EX b | (EX c,d | cxbd en A) = EX b | (EX c | cxb en I(A)) = EX c,b | cxb en I(A) = x en S(I(A))
  • x en S(I(A)) = EX b,c | bxc en I(A) = EX b,c | (EX d | bxcd en A) = (a=cd) EX b | (EX a | bxa en A) = x en S(A)
  • x en F(S(A)) = EX b | bx en S(A) = EX b | (EX c,d | cbxd en A) = EX b | (EX d | bxd en F(A)) = EX b,d | bxd en F(A) = x en S(F(A))
  • x en S(F(A)) = EX b,c | bxc en F(A) = EX b,c | (EX d | dbxc en A) = (a=db) = (EX a,c | axc en A) = x en S(A)