⟸ pàgina anterior ⟸

Exercici 11 (Tasca 3).

(regular expressions, decidable properties)

Propietats decidibles sobre expressions regulars

Sigui L_r el llenguatge (regular) representat per l’expressió regular r. Donades dues expressions regulars r i s com a entrada, descriviu un algorisme per decidir si

1. L_{r}=L_{s}.
2. L_{r}\subseteq L_{s}.
3. L_{r}=\emptyset.
4. L_{r} és infinit.
5. L_{r}\cap L_{s}=\emptyset.
6. L_{r}\cap L_{s} és infinit.

Quin és el cost asimptòtic de l’algorisme proposat en funció del nombre de símbols de r i s?