Espressioni regolari (RE - Regular Expression)

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?
Si, 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.




Termini mancanti/suggerimenti ?

© Copyright 1997-2001 by Francesco Longo, flongo@dsi.unive.it

Homepage Dizionario Informatico