Si è già visto che, dato un DFA, è possibile costruire un NFA che riconosca lo stesso linguaggio. Adesso l’obiettivo è fare il viceversa: dato un NFA $N=\lang Q, \Sigma, \delta, q_0, F\rang$, si vuole costruire un DFA $D_N$ che riconosca lo stesso linguaggio riconosciuto da $N$.
L’idea è di costruire un DFA che simuli contemporaneamente tutte le possibili computazioni di $N$, usando una tecnica chiamata costruzione per sottoinsiemi.
Ad esempio, considerando l’NFA rappresentato dal diagramma
il suo albero di computazione sulla stringa $w=11101$ (già mostrato come esempio di precedenza) è:
Per “codificare” questa computazione in un DFA, si definiscono degli stati aventi una struttura interna più complessa rispetto a quelli visti finora, dando a ciascuno di essi un nome strutturato che mette insieme tutti gli stati di un livello dell’albero:
Per ogni transizione del DFA:
Questo esempio è stato fatto seguendo una specifica computazione dell’NFA. Adesso, invece, bisognerà dare una costruzione generale, che consideri tutte le possibili evoluzioni dell’automa. Tale costruzione, come già anticipato, si chiama costruzione per sottoinsiemi in quanto, come si vede dall’esempio, i nomi degli stati del DFA sono sottoinsiemi dell’insieme $Q$ di stati dell’NFA. Una volta stabiliti gli stati, questa costruzione dovrà poi considerare come definire la fuznione di transizione e la condizione di accettazione del DFA: la soluzione per entrambi questi aspetti sarà essenzialmente ragionare sui singoli stati dell’NFA impacchettati nei nomi degli stati del DFA.
Dato un generico NFA $N = \lang Q, \Sigma, \delta, q_0, F\rang$, si costruisce il DFA $D_N=\lang Q_D, \Sigma, \delta_D, \{q_0\}, F_D\rang$, dove:
L’alfabeto di input $D_N$ è lo stesso dell’NFA $N$ (mentre tutte le altre componenti dell’automa cambiano), cosa necessaria perchè i due possano riconoscere il medesimo linguaggio.
L’insieme degli stati è $Q_D = 2^Q$, cioè l’insieme di tutti i sottoinsiemi di $Q$, ovvero di tutti i possibili sottoinsiemi di stati dell’NFA. Infatti, per la definizione di DFA l’unica cosa che importa degli stati è la struttura che la funzione di transizione definisce su di essi; i loro nomi possono essere fatti in qualunque modo, e qui in particolare sono insiemi, sottoinsiemi di $Q$ (ad esempio, potrebbe esserci uno stato chiamato $\{q_0, q_1, q_2\}$).
Il nome dello stato iniziale è l’insieme che contiene il solo stato iniziale $q_0$ dell’NFA: intuitivamente, osservando l’esempio precedente, si ha che le computazioni dell’NFA e del DFA partono di fatto dallo stesso stato, ma i nomi degli stati del DFA devono essere insiemi, quindi non si può mettere come stato iniziale direttamente $q_0$, ma piuttosto bisogna mettere $\{q_0\}$ (che va bene perchè è appunto un sottoinsieme di $Q$).
L’insieme degli stati finali è
$$ F_D = \{S \in Q_D \ | \ S \cap F \neq \empty\} $$
cioè comprende tutti e soli gli stati del DFA i cui nomi contengono almeno uno stato finale dell’NFA.