Diferencia entre revisiones de «Práctica 2: Expresiones regulares (Teoría de Lenguajes)»

De Cuba-Wiki
Línea 39: Línea 39:
( regla1: R=S.R|T y ¬(λ E S) -> R=S*.T )
( regla1: R=S.R|T y ¬(λ E S) -> R=S*.T )


*1)Armamos el sist. de ecuaciones y despejamos:
*2)Armamos el sist. de ecuaciones y despejamos:
**L1=a.L2|b.L3 = a.L2|b.(a|b)L2 = (a|b(a|b))L2
**L1=a.L2|b.L3 = a.L2|b.(a|b)L2 = (a|b(a|b))L2
**L2=a.L1|b.L2|λ = (a|b(a|b))L2|b.L2|λ = ((a|b(a|b))|b).L2|λ =(regla1) = ((a|b(a|b))|b)*|λ = ((a|b(a|b))|b)*
**L2=a.L1|b.L2|λ = (a|b(a|b))L2|b.L2|λ = ((a|b(a|b))|b).L2|λ =(regla1) = ((a|b(a|b))|b)*|λ = ((a|b(a|b))|b)*

Revisión del 01:25 15 abr 2008

Plantilla:Back

Ejercicio 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(0(1|λ))| D01(1+) = D01(0).(1|λ) | D01(1).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) = L2 (...)
    • 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|b(a|b))L2|b.L2|λ = ((a|b(a|b))|b).L2|λ =(regla1) = ((a|b(a|b))|b)*|λ = ((a|b(a|b))|b)*
    • L3=a.L2|b.L2 = (a|b)L2
    • ->L1=(a|b(a|b))((a|b(a|b))|b)*

Ejercicio 05

Ejercicio 06

Ejercicio 07

Ejercicio 08

Ejercicio 09

Ejercicio 10