Conversione da NDFA a DFA

Dichiarazione problema

Permettere X = (Qx, ∑, δx, q0, Fx)essere un NDFA che accetta il linguaggio L (X). Dobbiamo progettare un DFA equivalenteY = (Qy, ∑, δy, q0, Fy) tale che L(Y) = L(X). La procedura seguente converte l'NDFA nel suo DFA equivalente:

Algoritmo

Input - Un NDFA

Output - Un DFA equivalente

Step 1 - Crea una tabella di stato dal dato NDFA.

Step 2 - Creare una tabella di stato vuota sotto i possibili alfabeti di input per il DFA equivalente.

Step 3 - Contrassegna lo stato iniziale del DFA con q0 (uguale all'NDFA).

Step 4- Trova la combinazione di Stati {Q 0 , Q 1 , ..., Q n } per ogni possibile alfabeto di input.

Step 5 - Ogni volta che generiamo un nuovo stato DFA sotto le colonne alfabetiche di input, dobbiamo applicare nuovamente il passaggio 4, altrimenti andare al passaggio 6.

Step 6 - Gli stati che contengono uno degli stati finali dell'NDFA sono gli stati finali dell'equivalente DFA.

Esempio

Consideriamo l'NDFA mostrato nella figura seguente.

q δ (q, 0) δ (q, 1)
un {a, b, c, d, e} {d, e}
b {c} {e}
c {b}
d {e}
e

Utilizzando l'algoritmo di cui sopra, troviamo il suo equivalente DFA. La tabella degli stati di DFA è mostrata di seguito.

q δ (q, 0) δ (q, 1)
[un] [a, b, c, d, e] [d, e]
[a, b, c, d, e] [a, b, c, d, e] [b, d, e]
[d, e] [e]
[b, d, e] [c, e] [e]
[e]
[c, e] [b]
[b] [c] [e]
[c] [b]

Il diagramma di stato del DFA è il seguente: