Costruzione di un DFA dato un NFA

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

Untitled

il suo albero di computazione sulla stringa $w=11101$ (già mostrato come esempio di precedenza) è:

Untitled

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:

Untitled

Per ogni transizione del DFA:

  1. si considerano le possibili transizioni dell’NFA a partire da ciascuno degli stati $q_i$ “impacchettati” nel nome dello stato del DFA
  2. si raccolgono tutti stati di arrivo dell’NFA nel nome dello stato di arrivo 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.

Costruzione per sottoinsiemi

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: