Espressioni regolari (continua)

            

b) (u(ru+su+E)*)* = (ur+us)*u* ?
nota: E = epsilon.

SOLUZIONE b)

Semplifichiamo (u(ru+su+E)*)*

(u(ru+su+E)*)*  = (u(ru+su)*)* dato che con * posso generare E: E + r* = E U r* = r*

In questo caso per dimostrare la non uguaglianza e' sufficiente cercare 
una stringa di una RE che non appartiene all'altra RE.
ur per esempio e' generabile dalla RE di destra ma non da quella di sinistra.


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


SOLUZIONE c)

Dimostriamo se vale o meno l'uguaglianza con la doppia inclusione.

Come abbiamo visto nell'esercizio a), il fatto che 
(u*+r*s*)* C (r+s+u)* e' 
banale dato che (r+s+u)* puo' generare TUTTE le stringhe in r, s, u, E compresa.

Dimostriamo l'inclusione nell'altro senso:

(r+s+u)* C (u*+r*s*)* ?
 
Riscriviamo l'espressione regolare in questa forma:
(u*+r*s*)* = (u*+(r*s*)*)* dato che vale la proprieta' per cui r* = (r*)* 
poiche' per la (2) dell'esercizio a) si ha (r*s*)* = (r+s)* 
(u*+(r*s*)*)* = (u*+(r+s)*)*
(u*+(r+s)*)* = (u+r+s)*
 
 quindi (u*+r*s*)* = (u+r+s)*.

© 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