Espressioni regolari

Date le espressioni regolari r,s,u determinare giustificandolo formalmente, 
se valgono le seguenti proprieta':

 a) (u*(r*(s*)*)*)* = (r+(s+u)*)*;
 b) (u(ru+su+E)*)* = (ur+us)*u*;
 c) (u*+r*s*)* = (r+s+u)*.
 
nota: E = epsilon.


SOLUZIONE a)

(u*(r*(s*)*)*)* = (u*(r*s*)*)*  perche'    (s*)* = s*        (1)
   (u*(r*s*)*)* = (u*(r+s)*)*   perche'    (r*s*)* = (r+s)*  (2)
    (u*(r+s)*)* = (u+(r+s))*    per la (2)
                = (u+r+s)*       
               
dopo questa semplificazione riscriviamo la domanda:     
         ?
(u+r+s)* = (r+(s+u)*)*

Per verificare l'uguaglianza deve valere la doppia inclusione;


(r+(s+u)*)* C (u+r+s)*       

E'vero?

Sì, e' vero perche'  (u+r+s)* e' un espressione regolare che definisce un 
linguaggio composto da QUALSIASI tipo di stringa in r, s e u, stringa vuota
compresa.
 
Dimostriamo l'inclusione nell'altro senso, questa volta per induzione su n. E' vero che

(u+r+s)n C (r+(s+u)*)* ?

(CASO BASE) Per n = 1 si ha:

r e (r+(s+u)0)1)
s e (r+(s+u)1)1)
u e (r+(s+u)1)1)

(PASSO INDUTTIVO) Per n>0 si ha:
(u+r+s)n = (u+r+s)n-1(u+r+s)
Per ipotesi induttiva  (u+r+s)n-1C (r+(s+u)*)*
ed e' vero pure che
(u+r+s)n-1u C (r+(s+u)*)*
(u+r+s)n-1r C (r+(s+u)*)*
(u+r+s)n-1s C (r+(s+u)*)*
quindi si ha che:
(u+r+s)n-1(u+r+s)C (r+(s+u)*)*
Ma allora 
(u+r+s)nC (r+(s+u)*)*

Dalle due inclusioni:

(u+r+s)* = (r+(s+u)*)*      

C.V.D.

© C o p y r i g h t     1 9 9 4 - 2 0 0 4 w w w . d i z i o n a r i o i n f o r m a t i c o . c o m