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 -