assalamualaikum.......... hi guys kali ini aku bakalan bahas tentang nfa ke dfa udah pada tau belom apa itu dfa dan nfa , kalo belum check aja postingan aku sebelumnya yah heheheh , nah kalo sekarang kita belajar mengubah nfa ke dfa , nggak usah lama-lama lagi langsung aja check this out
Contoh soal :
Buatlah DFA yang Equevalen dengan NFA berikut ini :
Konfigurasi NFA secara formal adalah sebagai
berikut :
Q = {q0, q1 }
S = {a, b}
S = q0
F = {q1}
Fungsi-fungsi transisinya sebagai berikut :
d (q0, a) =
{q0,q1},
d (q0, b) =
q1,
d (q1, a) =
q1,
d (q1, b) =
q1,
Jika disajikan dalam tabel transisi :
d
|
a
|
b
|
q0
|
{q0,q1}
|
{q1}
|
q1
|
{q1}
|
{q1}
|
Konversi dari NFA ke DFA
Berdasarkan tabel
transisi pada NFA, kita gambarkan diagram transisi DFA nya terlebih dahulu .
Kemudian tentukan arah dua busur keluar untuk State {q0,q1} yaitu busur
arah ‘a’ dan ‘b’. Hal ini karena untuk DFA masing masing state harus memiliki pasangan
busur, dalam soal ini busur ‘a’ dan ‘b’.
Busur arah ‘a’
:
d ({q0,q1}, a) = {q0,a} È {q1,a}
= {q0,q1} È {q1}
= {q0,q1}
Busur arah ‘b’
:
d ({q0,q1}, b) = {q0,b} È {q1,b}
= {q1} È {q1}
= {q1}
Selanjutnya menentukan
state akhir, yaitu kita ingat bahwa F = {q1} ketika masih NFA maka himpunan
state akhir (F) sekarang adalah semua yang mengandung state q1.
Maka, F =
{{q1}, {q0, q1}}
Gambar Diagram Transisi Akhir setelah di konversi ke DFA
sekian dulu postingan kali ini , aku harap kalian ngerti yahhh ehehehehe , maaf jika ada salah , byeeeeee
assalamualaikum wr.wb............................................
Tidak ada komentar:
Posting Komentar