Diferencia entre revisiones de «Práctica 0: Preliminares (Teoría de Lenguajes)»

De Cuba-Wiki
Línea 99: Línea 99:


==Ejercicio 10==
==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)
*c)
*d)
*e)
*f)

Revisión del 03:15 30 mar 2007

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: λ Σ*, Σ^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

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

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}

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)
  • c)
  • d)
  • e)
  • f)