Minimizzazione di DFA

In Teoria degli automi (branca dell'Informatica) è detto minimizzazione di un DFA il procedimento che trasforma un dato automa a stati finiti deterministico (in breve DFA) nel DFA equivalente che ha il minor numero di stati. Due DFA sono detti equivalenti se riconoscono lo stesso linguaggio formale. Ci sono diversi algoritmi che producono il minimo DFA partendo da uno dato, con diversi metodi e complessità.

DFA minimo modifica

Esiste, per ogni linguaggio regolare che può essere accettato da un DFA, uno e un solo automa minimo, ovvero un DFA che ha il minimo numero di stati.[1] Lavorare sull'automa minimo è conveniente in termini di complessità computazionale per quegli algoritmi che lo utilizzano per i più svariati scopi, come il pattern matching.

Per ridurre un DFA si identificano al suo interno due tipi di stati, che possono essere uniti o eliminati senza che ciò influisca sul linguaggio accettato dall'automa stesso:

  • Stati irraggiungibili: stati dell'automa che in nessun caso possono essere raggiunti dallo stato iniziale; ovvero, stati (diversi dallo stato iniziale) che non hanno transizioni entranti, o stati in cui ogni transizione entrante parte da uno stato irraggiungibile.
  • Stati non distinguibili: stati che non possono essere distinti da un altro stato per nessuna delle possibili stringhe del linguaggio.

La minimizzazione avviene in tre passi, in cui si rimuovono o si uniscono tra loro gli stati di cui sopra. Essa culmina sempre con l'eliminazione degli stati non distinguibili, in quanto si tratta dell'operazione più dispendiosa.

Stati irraggiungibili modifica

Sia

 

un automa determinista completo. In questa definizione,   è l'insieme degli stati,   è l'alfabeto,   è la funzione di transizione che mappa uno stato ed un simbolo dell'alfabeto in uno stato,   è lo stato iniziale e   è l'insieme degli stati terminali accettori.

Due stati   e   appartenenti a  , sono detti indistinguibili se tutte le parole   riconosciute da   partendo da   sono anche riconosciute partendo da   e vice-versa. Formalmente, se per ogni parola   :

 .

Due stati sono separabili se non sono inseparabili. Vale il seguente criterio di minimizzazione:

Un automa finito deterministico completo e accessibile è minimo se e soltanto se i suoi stati sono due a due separabili.

L'equivalenza di Nerode è la relazione denotata  , sull'insieme degli stati e definita da

  .

Due stati equivalenti per la precedente relazione sono indistinguibili e vice-versa. Un automa è minimo quando l'equivalenza di Nerode è l'uguaglianza.

Algoritmo del calcolo degli stati raggiungibili/irraggiungibili modifica

Lo stato   di un automa finito deterministico   è irraggiungibile se non esiste alcuna parola   per la quale  . Denotiamo qui   l'estensione della funzione a tutte le stringhe. Gli stati raggiungibili possono essere ottenuti col seguente algoritmo:

let reachable_states := {q0};
let new_states := {q0};
do {
    temp := ;
    for each q in new_states do
        for each c in Σ do
            temp := temp  {p such that p = δ(q,c)};
        end;
    end;
    new_states := temp \ reachable_states;
    reachable_states := reachable_states  new_states;
} while (new_states  );
unreachable_states := Q \ reachable_states;

Gli stati irraggiungibili possono essere rimossi dal DFA senza influenzare il linguaggio che questi accetta.

Note modifica

  1. ^ Alfred V. Aho, Monia S. Lam, Ravi Sethi, Jeffrey D. Ullman, Capitolo 3.9.6 - Minimizing the number of States of a DFA, in Compilers. Principles, Techniques and Tools, 2ª ed., Pearson Education, 2006.
  Portale Informatica: accedi alle voci di Wikipedia che trattano di informatica