Práctica 2: Expresiones regulares (Teoría de Lenguajes)

De Cuba-Wiki

Plantilla:Back

Ejercicio 01

  • e) a+.b+.(cd)*
  • f) a*.b+ | cd.(cdcd)+
  • g) a.(a|b)*.c+
  • h) 1*(\|0)|(1*01)*
  • i) (0|1)*(00)(0|1)*
  • a) (+|-)(pd*|0)(,d*p|λ) siendo p=(1|...|9) y d=(0|...|9)
  • b) (+|-)p(,d*p|λ)x10^(+|-)(pd*|d)
  • c) l((l|d)*|-(l|d))*
  • h) 1*(0|λ)(1+01*)*

Ejercicio 02

(Revisar)

  • a) D1(10*1) = D1(1).(0*1) = λ.(0*1) = 0*1
  • b) Dλ(10*1) = Dλ(1).(0*1) = 1.0*1
  • c) D0(10*1) = D0(1).(0*1) = Ø.(0*1) = Ø
  • d) Da(ab*|ac|c+) = Da(ab*)|Da(ac)|Da(c+)= Da(a).(b*)|Da(a).c|Da(c).c* = λ.b*|λ.c|Ø.c* = b*|c
  • e) Da(a+ba) = Da(a+).ba = Da(a).a*.(ba) = λ.a*.ba = a*ba
  • f) Da(a*ba) = Da(a*).ba | Da(ba) = Da(a).a*.ba | Da(b).a = λ.a*ba | Ø.a = a*ba
  • g) D01(0(1 | λ) | 1+) = D01(01 | 0)| D01(1+) = (λ | Ø) | D01(1).1* = λ | Ø.1* = λ

Ejercicio 03

  • 1) Tomando L0 = (0|1)*.01 :
    • d0(L0) = [ d0((0|1)*).01 ] | d0(01) = [ d0(0|1).(0|1)*.01 ] | [ d0(0).1 ] = [ (d0(0)|d0(1)).(0|1)*.01 ] | [ d0(0).1 ] = [ (d0(0)|d0(1)).(0|1)*.01 ] | 1 = [ (0|1)*.01 ] | 1 = L0 | 1 = L1
    • d1(L0) = [ d1((0|1)*).01 ] | d1(01) = [ d1(0|1).(0|1)*.01 ] | d1(0).1 = [ (d1(0)|d1(1)).(0|1)*.01 ] = [ (0|1)*.01 ] = L0 (...)
    • d00(L0) = d0d0(L0) = d0(L1) = d0(L0|1) = d0(L0)|d0(1) = L1 (...)
    • d01(L0) = d1d0(L0) = d1(L1) = d1(L0|1) = d1(L0)|d1(1) = L0|λ = L2 (Final)
    • d010(L0) = d0d1d0(L0) = d0d1(L1) = d0(L2) = d0(L0|λ) = d0(L0) = L1 (...)
    • d011(L0) = d1d1d0(L0) = d1d1(L1) = d1(L2) = d1(L0|λ) = d1(L0) = L0 (...)
    • d100(L0) = d0d0d1(L0) = d0d0(L0) = d0(L1) = d0(L0|1) = d0(L0) = L1 (...)
    • d101(L0) = d1d0d1(L0) = d1d0(L0) = d1(L1) = d1(L0|1) = d1(L0)|λ = L0|λ = L2 (...)
  • 2) Tomando L0 = a(b|λ)|b+ :
    • da(L0) = da(a(b|λ)) | da(b+) = da(a)(b|λ) | da(b)b* = b|λ = L1 (Final)
    • db(L0) = db(a(b|λ)) | db(b+) = db(a)(b|λ) | db(b)b* = b* = L2 (Final)
    • daa(L0) = dada(L0) = da(L1) = da(b|λ) = da(b)|da(λ) = Ø
    • dab(L0) = dbda(L0) = db(L1) = db(b|λ) = db(b)|db(λ) = λ = L3 (Final)
    • dba(L0) = dadb(L0) = da(L2) = da(b*) = Ø
    • dbb(L0) = dbdb(L0) = db(L2) = db(b*) = b* = L2 (...)

Ejercicio 04

  • 1)Armamos el sist. de ecuaciones y despejamos:
    • L0=a.L1|b.L1 = (a|b)L1
    • L1=a.L1|b.L0|λ = a.L1|b.(a|b)L1|λ = (a|b(a|b))L1|λ =(regla1) ((a|b(a|b))*.λ = ((a|b(a|b))*
    • -> L0=(a|b)L1=(a|b)((a|b(a|b))*

( regla1: R=S.R|T y ¬(λ E S) -> R=S*.T )

  • 2)Armamos el sist. de ecuaciones y despejamos:
    • L1=a.L2|b.L3 = a.L2|b.(a|b)L2 = (a|b(a|b))L2
    • L2=a.L1|b.L2|λ = a(a|b(a|b))L2|b.L2|λ = (a(a|b(a|b))|b).L2|λ =(regla1) = (a(a|b(a|b))|b)*|λ = (a(a|b(a|b))|b)*
    • L3=a.L2|b.L2 = (a|b)L2
    • ->L1=(a|b(a|b))(a(a|b(a|b))|b)*
  • 3)Armamos el sist. de ecuaciones y despejamos:
    • L0=aL1
    • L1=aL1|aL2 = (regla) a*aL2 = a+L2
    • ->L0=aa+L2
    • L2=aL3|bL2|λ
    • L3=(a|b)L3|bL0 = (a|b)L3|baa+L2 =(regla) (a|b)*baa+L2
    • ->L2=a(a|b)*baa+L2|bL2|λ = (a(a|b)*baa+|b)L2 |λ =(regla) (a(a|b)*baa+|b)*
    • ->L0=aa+(a(a|b)*baa+|b)* (se puede comprobar visualmente con el autómata)

Ejercicio 05

Ejercicio 06

Ejercicio 07

Ejercicio 08

Ejercicio 09

Ejercicio 10