Sabtu, 27 Mei 2017 NFA KE DFA ( TEORI BAHASA OTOMATA )

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