Chiusura dei linguaggi regolari
Un linguaggio L è regolare se e solo se esiste un automa A che lo accetta, cioè L(A) = L. Dimostreremo che i linguaggi regolari sono chiusi rispetto alle operazioni di unione, intersezione, concatenazione e chiusura di Kleene.
Chiusura di un insieme rispetto a un’operazione
Diciamo che un insieme M è chiuso rispetto all’operazione ⊗ se vale
Un esempio è l’addizione nell’insieme dei numeri naturali. La somma di due numeri naturali qualsiasi è di nuovo un numero naturale. Invece l’insieme dei numeri naturali non è chiuso rispetto alla sottrazione, perché ad esempio 7 − 15 = −8 e il numero −8 non è naturale.
Vedremo rispetto a quali operazioni è chiuso l’insieme dei linguaggi regolari. Tutte le dimostrazioni saranno costruttive, cioè costruiremo un automa che accetta il linguaggio risultante.
Capitoli: Chiusura dei linguaggi regolari, Unione di linguaggi regolari, Intersezione di linguaggi regolari, Differenza di linguaggi regolari, Complemento di un linguaggio regolare, Concatenazione di linguaggi regolari, Chiusura di Kleene di un linguaggio regolare
