Equivalenza automi AFD e AFN
Gli automi a stati finiti deterministici (DFA) e non deterministici (NFA) sono equivalenti.
L'automa deterministico DFA è un caso particolare degli automi NFA.
Quindi, il linguaggio accettato dall'automa DFA è un sottoinsieme del linguaggio accettato dell'automa NFA.
$$ L_m(DFA) ⊆ L_m(NFA) $$
Tuttavia, vale anche l'inverso
$$ L_m(NFA) ⊆L_m(DFA) $$
perché ogni automa non deterministico (NFA) ha un automa deterministico equivalente (DFA).
Esempio. Se in un NFA una stessa parola w è generata da diverse produzioni e raggiunge diversi stati x1,x2 e x3, è possibile creare in un DFA un unico stato x'1 composto dagli stati x1,x2 e x3. Ecco come trasformare un automa NFA in DFA.
Pertanto, vale la relazione di uguaglianza
$$ L_m(NFA) = L_m(DFA) $$
Un automa deterministico (DFA) e non deterministico (NFA) hanno lo stesso linguaggio accettato.
Quindi, uno stesso problema può essere affrontato con un automa DFA oppure con un automa NFA.
E' meglio un automa DFA o NFA?
La scelta tra DFA e NFA dipende soprattutto dalla semplicità di realizzazione dell'automa.
A parità di problema, un automa NFA e un automa DFA hanno un numero di stati e di transizioni differenti.
A volte è meglio l'automa DFA, altre volte l'automa NFA.
E così via.
