L’equivalenza tra modelli computazionali viene studiata sulla classe di linguaggi riconosciuti: due modelli sono equivalenti se e solo se riconoscono la stessa classe di linguaggi, ovvero se e solo se ogni linguaggio riconosciuto da uno dei due modelli può essere riconosciuto anche dall’altro modello.
E’ importante sottolineare che l’equivalenza è appunto su tutti i linguaggi riconosciuti dai due modelli: per dimostrarla, non è sufficiente mostrare che esiste uno specifico linguaggio riconosciuto da entrambi.
Si vuole dimostrare che i DFA e gli NFA riconoscono la stessa classe di linguaggi, cioè che la classe dei linguaggi regolari (per definizipne, quelli riconosciuti dai DFA) coincide con la classe dei linguaggi riconosciuti dagli NFA.
La dimostrazione verrà svolta in due passaggi, trattando separatamente i seguenti due fatti:
Un aspetto importante delle due dimostrazioni che verranno presentate è che sono entrambe costruttive: la dimostrazione del fatto 1 mostrerà concretamente come costruire l’NFA $N_D$ dato un DFA $D$, e viceversa per la dimostrazione del fatto 2.
Si consideri il DFA rappresentato dal seguente diagramma:
In quanto DFA, esso ha per ogni stato esattamente due transizioni uscenti, una etichettata con 0 e l’altra con 1. Si osserva però che lo stesso diagramma può anche essere interpretato come un NFA, con:
$Q = \{q_0, q_1, q_2\}$;
$\Sigma = \{0, 1\};$
stato iniziale $q_0$
$F=\{q_1\}$
funzione di transizione $\delta :\{q_0, q_1, q_2\}\times\{0, 1\}\rarr 2^{\{ q_0, q_1, q_2\}}$, definita dalla seguente tabella:
Si osserva che il valore di $\delta$ per ogni coppia stato-simbolo è sempre un insieme singoletto (contenente un unico stato): questa è una funzione d transizione “particolare”, ma comunque perfettamente coerente con la definizione degli NFA.
Quella appena presentata in modo informale è l’idea della costruzione di un NFA dato un DFA, ma bisogna sottolineare che il fatto di aver costruito l’NFA a partire dal DFA dato non dimostra in alcun modo che i due riconoscano lo stesso linguaggio.