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

Sorun bildirimi

İzin Vermek X = (Q_x, ∑, δ_x, q₀, F_x)L (X) dilini kabul eden bir NDFA olmak. Eşdeğer bir DFA tasarlamalıyızY = (Q_y, ∑, δ_y, q₀, F_y) ö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 ₀ , Q ₁ , ..., 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 -