Expressions regulars i propietats de tancament dels regulars
Sabem que les expressions regulars representen exactament els llenguatges regulars i que els llenguatges regulars són tancats per diverses operacions. Aquest exercici tracta de trobar expressions regulars per als llenguatges després d’aplicar-los una d’aquestes operacions.
Donades les expressions regulars r_1 i r_2 com a entrada, que representen respectivament els llenguatges L_1 i L_2, per construcció (r_1)+(r_2), (r_1)(r_2), and (r_1)^* representen els llenguatges L_1\cup L_2, L_1L_2 i L_1^* respectivament. Què es pot dir de les altres operacions que preserven la regularitat?
(complementari) Donada una expressió regular r com a entrada, que representa el llenguatge L, doneu un algorisme per trobar l’expressió regular que representa el llenguatge \overline{L}. Quin és el cost asimptòtic de l’algorisme proposat en funció del nombre de símbols de r?
(intersecció) Donades dues expressions regulars r_1 i r_2 com a entrada, que representen els llenguatges L_1 i L_2 respectivament, doneu un algorisme per trobar una expressió regular que representi el llenguatge L_1\cap L_2. Quin és el cost asimptòtic de l’algorisme proposat en funció del nombre de símbols de r_1 i r_2?
(revessat) Donada una expressió regular r com a entrada, que representa el llenguatge L, doneu un algorisme per trobar una expressió regular que representi el llenguatge L^R. Quin és el cost asimptòtic de l’algorisme proposat en funció del nombre de símbols de r?
(homomorfisme) Donada una expressió regular r com a entrada, que representa el llenguatge L, i un homomorfisme \sigma, doneu un algorisme per trobar una expressió regular que representi el llenguatge \sigma(L).
(homomorfisme invers) Donada una expressió regular r com a entrada, que representa el llenguatge L, i un homomorfisme \sigma, doneu un algorisme per trobar una expressió regular que representi el llenguatge \sigma^{-1}(L).