Conversione da NDFA a DFA

Dichiarazione problema

Permettere X = (Q_x, ∑, δ_x, q₀, F_x)essere un NDFA che accetta il linguaggio L (X). Dobbiamo progettare un DFA equivalenteY = (Q_y, ∑, δ_y, q₀, F_y) 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 ₀ , Q ₁ , ..., 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: