Edición de «Práctica 2: Expresiones regulares (Teoría de Lenguajes)»

{{Back|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) = &lambda;.(0*1) = 0*1
*b) D&lambda;(10*1) = D&lambda;(1).(0*1) = 1.0*1
*c) D0(10*1) = D0(1).(0*1) = &Oslash;.(0*1) = &Oslash;
*d) Da(ab*|ac|c+) = Da(ab*)|Da(ac)|Da(c+)= Da(a).(b*)|Da(a).c|Da(c).c* = &lambda;.b*|&lambda;.c|&Oslash;.c* = b*|c
*e) Da(a+ba) = Da(a+).ba = Da(a).a*.(ba) = &lambda;.a*.ba = a*ba
*f) Da(a*ba) = Da(a*).ba | Da(ba) = Da(a).a*.ba | Da(b).a = &lambda;.a*ba | &Oslash;.a = a*ba
*g) D01(0(1 | &lambda;) | 1+) = D01(01 | 0)| D01(1+) = (&lambda; | &Oslash;) | D01(1).1* = &lambda; | &Oslash;.1* = &lambda;

==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|&lambda; = L2 (Final)
**d010(L0) = d0d1d0(L0) = d0d1(L1) = d0(L2) = d0(L0|&lambda;) = d0(L0) = L1 (...)
**d011(L0) = d1d1d0(L0) = d1d1(L1) = d1(L2) = d1(L0|&lambda;) = 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)|&lambda; = L0|&lambda; = L2 (...)

*2) Tomando L0 = a(b|&lambda;)|b+ :
**da(L0) = da(a(b|&lambda;)) | da(b+) = da(a)(b|&lambda;) | da(b)b* = b|&lambda; = L1 (Final)
**db(L0) = db(a(b|&lambda;)) | db(b+) = db(a)(b|&lambda;) | db(b)b* = b* = L2 (Final)
**daa(L0) = dada(L0) = da(L1) = da(b|&lambda;) = da(b)|da(&lambda;) = &Oslash;
**dab(L0) = dbda(L0) = db(L1) = db(b|&lambda;) = db(b)|db(&lambda;) = &lambda; = L3 (Final)
**dba(L0) = dadb(L0) = da(L2) = da(b*) = &Oslash;
**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|&lambda; = a.L1|b.(a|b)L1|&lambda; = (a|b(a|b))L1|&lambda; =(regla1) ((a|b(a|b))*.&lambda; = ((a|b(a|b))*
**-> L0=(a|b)L1=(a|b)((a|b(a|b))*

( regla1: R=S.R|T y &not;(&lambda; E S) -> R=S*.T )

*1)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|&lambda; = a(a|b(a|b))L2|b.L2|&lambda; = (a(a|b(a|b))|b).L2|&lambda; =(regla1) = (a(a|b(a|b))|b)*|&lambda; = (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|&lambda;
**L3=(a|b)L3|bL0 = (a|b)L3|baa+L2 =(regla) (a|b)*baa+L2
**->L2=a(a|b)*baa+L2|bL2|&lambda; = (a(a|b)*baa+|b)L2 |&lambda; =(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==

[[Category:Prácticas]]