NDFA'dan DFA'ya Dönüştürme

Sorun bildirimi

İzin Vermek X = (Qx, ∑, δx, q0, Fx)L (X) dilini kabul eden bir NDFA olmak. Eşdeğer bir DFA tasarlamalıyızY = (Qy, ∑, δy, q0, Fy) öyle ki L(Y) = L(X). Aşağıdaki prosedür, NDFA'yı eşdeğer DFA'ya dönüştürür -

Algoritma

Input - Bir NDFA

Output - Eşdeğer bir DFA

Step 1 - Verilen NDFA'dan durum tablosu oluşturun.

Step 2 - Eşdeğer DFA için olası giriş alfabelerinin altında boş bir durum tablosu oluşturun.

Step 3 - DFA'nın başlangıç ​​durumunu q0 ile işaretleyin (NDFA ile aynı).

Step 4- Olası her giriş alfabesi için Durumların {Q 0 , Q 1 , ..., Q n } kombinasyonunu bulun .

Step 5 - Giriş alfabesi sütunlarının altında her yeni DFA durumu oluşturduğumuzda, 4. adımı tekrar uygulamalıyız, aksi takdirde 6. adıma gitmeliyiz.

Step 6 - NDFA'nın son durumlarından herhangi birini içeren durumlar, eşdeğer DFA'nın son durumlarıdır.

Misal

Aşağıdaki şekilde gösterilen NDFA'yı ele alalım.

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

Yukarıdaki algoritmayı kullanarak eşdeğer DFA'yı buluruz. DFA'nın durum tablosu aşağıda gösterilmektedir.

q δ (q, 0) δ (q, 1)
[a] [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]

DFA'nın durum diyagramı aşağıdaki gibidir -