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: