Contoh Mengubah NFA menjadi DFA

Misal diketahui suatu NFA dengan alfabet {0, 1}, himpunan state {a, b, c, d}, inisial state a, final state {a, c} dengan relasi transisinya Δ = {((a,101),b), ((a, Λ),d), ((b,1),b), ((b,0),d), ((b,11,),c), ((b, Λ),c), ((d,1),c)}. Dan kita ingin mengubah NFA di atas menjadi DFA yang ekuivalen. Pertama kita gambar dahulu NFA berdasar spesifikasi di atas. Lingkaran yang terdapat lingkaran di dalamnya adalah initial state. Lingkaran yang terdapat kotak di luarnya adalah final state.

Selanjutnya kita lakukan tahap perubahan ke DFA dengan mentrace jalannya NFA.

Setelah terlihat seperti grafik di atas, kita rename state-state yang ada agar lebih simple.

Dan, jadilah DFA yang ekuivalen dengan NFA sebelumnya. Mari kita cek bagaimana bila kita memasukkan suatu string ke DFA tersebut.
Misal kita pilih string sepanjang 8 bit: 10101100. Bila kita telusurkan, maka final state yang dikunjungi ada state B.

Disclaimer: tulisan di atas diperuntukkan catatan pribadi. Perlu dipahami bahwasanya untuk menggunakan tulisan ini sebagai sumber referensi  pembaca perlu memahami terlebih dahulu konsep NFA dan DFA. Sehingga tidak tersesat dengan membaca tulisan ini :p

Leave a Reply