Come sappiamo i linguaggi regolari sono chiusi rispetto a:
a) prodotto (giustapposto): L1 x L2 = {u.v | u Î L1, v Î L2} è linguaggio regolare;
b) unione: L1 È L2 è linguaggio regolare;
c) complemento: L = {u | u Î S*-L} è linguaggio regolare;
d) intersezione: L1 Ç L2 è linguaggio regolare;
assunti L, L1, L2 linguaggi regolari su S.
Per i casi a) e b) è immediato, dati automi per L1 ed L2, ottenere automi per L1xL2 ed L1 È L2. Si dia un procedimento per ottenere un automa nei casi c) e d). Ovvero si risolvano i seguenti esercizi:
1) Sia A un automa per il linguaggio regolare L, si dia un procedimento per generare un automa A per il linguaggio L, complemento di L su S.
2) Siano A1 ed A2 automi per, rispettivamente, il linguaggio regolare L1 e il linguaggio regolare L2, si dia un procedimento per generare un automa A1ÇA2 per il linguaggio regolare L1 Ç L2, intersezione dei linguaggi L1 ed L2.
3) Come sappiamo, le espressioni regolari hanno la stessa potenza degli automi a stati finiti, ovvero descrivono la stessa classe di linguaggi descritta dagli automi a stati finiti, cioè la classe dei linguaggi regolari. La usuale definizione di espressione regolare prevede i soli operatori di giustapposizione “.”, altenato “|”, potenza finita, “_k”, potenza limite o stella di Kleene, “_*”. Esistono però definizioni, come quelle adottate nei sistemi LEX o in linguaggi come PERL, che includono anche operatori di negazione “~”, e di congiunzione “&”. Queste definizioni introducono una classe di espressioni più potente di quella usuale?
Ultimo aggiornamento 7 Marzo 2202 |