Minimizzazione di DFA

Questa voce o sezione sull'argomento Informatica è stata parzialmente tradotta dalla lingua inglese.

---

Puoi contribuire terminando la traduzione o usando altre fonti. Non usare programmi di traduzione automatica. Usa {{Tradotto da}} quando hai terminato. Se nella pagina di modifica trovi del testo nascosto, controlla che sia aggiornato servendoti dei collegamenti «in altre lingue» in fondo alla colonna di sinistra. Segui i suggerimenti del progetto di riferimento.

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à.