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

De Cuba-Wiki
Saltar a: navegación, buscar
Back.png Volver a la página de la materia

Ejercicio 01[editar]

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

Ejercicio 02[editar]

  • x = λ
  • x = abb
  • x = abbabb
  • x = abbabbabb
  • П{k=0..3} x = λ.x.xx.xxx = x
  • x = bba

Ejercicio 03[editar]

Valen:

Ejercicio 04[editar]

  • xy = abbacb
  • (xy) = bcabba
  • y = bca
  • y.x = (xy)
  • λx = x
  • λy = y
  • xλy = xy
  • x.y = x.y = abbabbacbacb

Ejercicio 05[editar]

  • Σ A = {a,b,c}
  • Σ 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[editar]

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

Ejercicio 07[editar]

  • 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[editar]

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

Ejercicio 09[editar]


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[editar]

  • 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)