Upload
migdalis
View
217
Download
0
Embed Size (px)
Citation preview
7/26/2019 Formula Rio Ly c
1/1
Propiedades bsicas de los operadores en
trminos de equivalencia de expresionesregulares
1) asociatividad de + :
(r + s) + t r + (s + t)
2) conmutatividad de + :
r + s s + r
3) idempotencia de + :r + r r
) elemento neutro de + :r + ! r ! + r
) asociatividad de :
(r " s) " t r" (s " t)
#) elemento neutro de :
r " 1 r 1 " r
$) cero de :r " ! ! ! " r
%) distributividad de con respecto a + :(r + s) "t r " t + s " t
t " (r + s) t " r + t " s
&) propiedades de :
r r " r r (r )
r 1 + r " r
Para todo a '
sem: * ' P (' )sem (!) , -
sem (1) , ./0sem (a) , .a0
sem
(r + s) ,sem
(r) sem
(s)sem (r " s) , sem (r) sem (s)
sem (r ) , sem (r)
e deine entonces la relaci4n de
equivalencia en * ' :r s sem(r) , sem (s)
Derivada de una expresin regular:5a : * ' * '
5a! !5a1 !
5ab .1 si a , b
! si a , b
5a(r + s) 5ar + 5as
5a(r " s) (5ar) " s + 6 (r) " 5as5a(r ) (5ar) " r
que cumple7 por 8ip4tesis7 la siguiente
propiedad: para todo r * 'sem (5ar) , 5a(sem (r))