Maaf, Anda mengaktifkan Adblock pada browser anda!
Atau anda tidak mengaktifkan Javascript![ Disable Your AdBlock Please ]
Home > Teori Bahasa dan Automata > Konversi dari NFA ke DFA

Konversi dari NFA ke DFA

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


8 comments

  1. makasiih yaaa 🙂
    membantu banget niih buat nambah latihan

  2. iya sama-sama, semoga bermanfaat..:)

  3. btw mintol…. gimana bhs.mesin elevator/lift 1-4 lantai….? mksudQ dibuat dlm bhs.outomata…….

    klo bisa mintol bantuanx….

  4. Wah terma kasih nih mas.
    Dapat pencerahan dikit.
    sempat mumet materi dapat tugas kuliah tntang DFA dan NFA ini.

  5. iya sama-sama, semoga bermanfaat.. 🙂

  6. contoh konversi NFA yg lain donk…..:)

  7. Kak klo ada q0 sd q4 nanti ada state q0,q1,q2,q3,q4 gitu?

Leave a Reply

Your email address will not be published. Required fields are marked *

*