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

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)