Konversi NDFA ke DFA

Pernyataan masalah

Membiarkan X = (Qx, ∑, δx, q0, Fx)menjadi NDFA yang menerima bahasa L (X). Kami harus merancang DFA yang setaraY = (Qy, ∑, δy, q0, Fy) seperti yang L(Y) = L(X). Prosedur berikut mengubah NDFA menjadi DFA yang setara -

Algoritma

Input - NDFA

Output - DFA setara

Step 1 - Buat tabel status dari NDFA yang diberikan.

Step 2 - Buat tabel status kosong di bawah abjad masukan yang mungkin untuk DFA yang setara.

Step 3 - Tandai status awal DFA dengan q0 (Sama seperti NDFA).

Step 4- Cari tahu kombinasi Serikat {Q 0 , Q 1 , ..., Q n } untuk setiap alfabet masukan yang mungkin.

Step 5 - Setiap kali kami membuat status DFA baru di bawah kolom alfabet masukan, kami harus menerapkan langkah 4 lagi, jika tidak lanjutkan ke langkah 6.

Step 6 - Negara bagian yang berisi salah satu status akhir NDFA adalah status akhir dari DFA setara.

Contoh

Mari kita perhatikan NDFA yang ditunjukkan pada gambar di bawah ini.

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

Dengan menggunakan algoritma di atas, kami menemukan DFA yang setara. Tabel status DFA ditunjukkan di bawah ini.

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

Diagram status DFA adalah sebagai berikut -