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

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


==Ejercicio 03==
==Ejercicio 03==
Valen: λ <math>\in</math> Σ*, Σ^0 = {λ}
Valen: <math>\lambda \in \Sigma*, \Sigma^0 = \{\lambda\}</math>


==Ejercicio 04==
==Ejercicio 04==

Revisión del 14:45 2 jun 2011

Plantilla:Back

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:

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

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