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

{{Back|Teoría de Lenguajes}}

==Ejercicio 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) = L2 (...)
**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 )

*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|&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)*

==Ejercicio 05==
==Ejercicio 06==
==Ejercicio 07==
==Ejercicio 08==
==Ejercicio 09==
==Ejercicio 10==

[[Category:Prácticas]]
@@ Línea 2: / Línea 2: @@
 ==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)
@@ Línea 30: / Línea 18: @@
 **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 (...)
+**d010(L0) = d0d1d0(L0) = d0d1(L1) = d0(L2) = d0(L0|&lambda;) = d0(L0) = L2 (...)
 **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 (...)
@@ Línea 56: / Línea 44: @@
 **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==