Minimizzazione di un automa

Per minimizzazione di un automa intendiamo la ricerca di un automa equivalente che contenga il minor numero possibile di stati. Anche un automa privo di stati inutili può essere semplificato ulteriormente.

Esempio

Prendiamo questo automa:

L’automa accetta solo le parole 01 e 11. Eppure è evidente che esiste un automa più semplice con tre stati che accetta lo stesso linguaggio. Gli stati q₁ e q₂ si possono fondere in un unico nuovo stato {q₁, q₂}; le transizioni che entravano negli stati q₁ o q₂ entreranno nel nuovo stato, e lo stesso vale per le transizioni uscenti da q₁ e q₂. Otteniamo questo automa:

Questo automa accetta evidentemente lo stesso linguaggio del precedente e ha meno stati.

Equivalenza degli stati

Sia A = ⟨Q, Σ, δ, q₀, F⟩ un automa. Definiamo il linguaggio dello stato q ∈ Q, indicato con L(q), come

$L (q) = L (⟨ Q, Σ, δ, q, F ⟩)$

Cioè cambiamo lo stato iniziale dell’automa A da q₀ a q e calcoliamo il linguaggio accettato da questo automa. In altre parole, nel linguaggio L(q) ci sono tutte le parole w tali che nell’automa A dallo stato q con la parola w si arriva in uno stato finale. Tornando all’automa precedente, L(q₁) = {1}.

Diciamo che due stati distinti q₁ e q₂ sono equivalenti se vale

$L (q_{1}) = L (q_{2})$

Che cosa significa? Se gli stati q₁, q₂ sono equivalenti, se li rendiamo stati iniziali dell’automa, generano lo stesso linguaggio. In altre parole: se l’automa arriva nella configurazione ⟨q₁, w⟩ e ⟨q₂, w⟩, in entrambi i casi deve accettare oppure in entrambi i casi rifiutare.

Tornando all’automa precedente: gli stati q₁ e q₂ sono equivalenti, perché se siamo nello stato q₁ possiamo ancora accettare la parola in ingresso solo se la parte non letta è uguale a 1. Lo stesso vale se siamo nello stato q₂.

Minimizzare un automa significa quindi trovare gli stati equivalenti ed eliminarli fondendoli in un unico nuovo stato, proprio come abbiamo fatto nell’esempio precedente.

Come trovare gli stati equivalenti

Quali stati sicuramente non sono equivalenti? Uno stato finale e uno non finale sicuramente non sono equivalenti, perché il linguaggio di uno stato finale è diverso da quello di uno stato non finale: uno stato finale accetta di sicuro la parola ε, uno non finale no. Mostriamo subito il procedimento su un esempio. Prendiamo questo automa:

Cominciamo creando due insiemi di stati

$\begin{array}{rcl} S_{1} & = & F = {q_{3}, q_{6}}, \\ S_{2} & = & Q ∖ F = {q_{0}, q_{1}, q_{2}, q_{4}, q_{5}} . \end{array}$

Ora creiamo la tabella delle transizioni e conserviamo l’informazione sui gruppi S₁ e S₂:

$\begin{array}{ccccc} gruppo & stato & 0 & 1 \\ S_{1} & q_{3} & q_{5} & q_{4} \\ q_{6} & — & — \\ S_{2} & q_{0} & q_{1} & q_{2} \\ q_{1} & — & q_{3} \\ q_{2} & — & q_{3} \\ q_{4} & q_{6} & — \\ q_{5} & q_{6} & — \end{array}$

Ora modifichiamo la tabella: invece di scrivere direttamente in quali stati si va per un dato simbolo, annotiamo soltanto il gruppo in cui si arriva. Ad esempio dallo stato q₃ con 0 si arriva nello stato q₅, che è nel gruppo S₂. Al posto di q₅ scriviamo quindi nella tabella S₂:

$\begin{array}{ccccc} gruppo & stato & 0 & 1 \\ S_{1} & q_{3} & S_{2} & S_{2} \\ q_{6} & — & — \\ S_{2} & q_{0} & S_{2} & S_{2} \\ q_{1} & — & S_{1} \\ q_{2} & — & S_{1} \\ q_{4} & S_{1} & — \\ q_{5} & S_{1} & — \end{array}$

Ora dividiamo ulteriormente entrambi i gruppi. Mettiamo nello stesso gruppo gli stati che per tutti i simboli vanno negli stessi gruppi. Ad esempio gli stati q₃ e q₆ non staranno nello stesso gruppo, perché né per 0 né per 1 vanno nello stesso gruppo. Al contrario, gli stati q₁ e q₂ staranno nello stesso gruppo, perché nessuno dei due ha una transizione per 0 ed entrambi per 1 vanno nel gruppo S₁. Creiamo così nuovi gruppi:

$\begin{array}{ccccc} gruppo & stato & 0 & 1 \\ q_{3} & S_{2} & S_{2} \\ q_{6} & — & — \\ q_{0} & S_{2} & S_{2} \\ q_{1} & — & S_{1} \\ q_{2} & — & S_{1} \\ q_{4} & S_{1} & — \\ q_{5} & S_{1} & — \end{array}$

In ogni gruppo abbiamo le stesse transizioni. Etichettiamo i gruppi appena ottenuti e verifichiamo di nuovo verso quale di questi nuovi gruppi vanno gli stati:

$\begin{array}{ccccc} gruppo & stato & 0 & 1 \\ S_{1} & q_{3} & S_{5} & S_{5} \\ S_{2} & q_{6} & — & — \\ S_{3} & q_{0} & S_{4} & S_{4} \\ S_{4} & q_{1} & — & S_{1} \\ q_{2} & — & S_{1} \\ S_{5} & q_{4} & S_{2} & — \\ q_{5} & S_{2} & — \end{array}$

A questo punto proviamo a dividere di nuovo i gruppi. Vediamo però che non possiamo fare nessun’altra divisione: otterremmo gli stessi gruppi, perché gli stati q₁ e q₂ hanno sì le stesse transizioni rispetto ai gruppi, ma sono già nello stesso gruppo e nel gruppo S₄ non c’è nessun altro stato. L’algoritmo di ricerca degli stati equivalenti è terminato. Da ogni gruppo ci basta scegliere uno stato ed eliminare gli altri; tutte le transizioni che portavano negli stati eliminati porteranno ora nell’unico stato che abbiamo scelto.

Possiamo scegliere, ad esempio, che il nostro nuovo automa abbia gli stati q₃, q₆, q₀, q₁, q₄ ed eliminare gli stati q₂ e q₅. Tutte le transizioni che portavano in q₂ ora porteranno in q₁ e tutte quelle che portavano in q₅ porteranno in q₄:

Procedimento di minimizzazione di un automa

Eliminiamo gli stati irraggiungibili,
eliminiamo gli stati inutili,
eliminiamo gli stati equivalenti.

Fonti

Capitoli: Stati irraggiungibili, Stati inutili, Minimizzazione di un automa

« Precedente: Stati inutili

Successivo: Proprietà di chiusura dei linguaggi regolari »