Aplikasi Pemanfaatan DFA / NFA
Finite Automata
Finite Automata adalah mesin utama dari suatu bahasa reguler. Finite Automata memiliki jumlah state yang banyaknya berhingga dan dapat berpindah-pindah dari suatu state ke state yang lainnya. Finite Automata dibagi atas dua, yaitu Deterministic Finite Automata (DFA) dan Non-Deterministic Finite Automata (NFA).
Deterministic Finite Automata (DFA)
Pada Deterministic Finite Automata, jika suatu state diberi inputan maka state tersebut akan selalu tepat menuju satu state.
Non-Deterministic Finite Automata (NFA)
Jika suatu state diberi inputan maka mungkin saja bisa menuju ke beberapa state berikutnya.
Aplikasi Pemanfaatan : "Text Search"
Aplikasi satu ini sangat cocok dengan pembahasan permasalahan mengenai DFA dan NFA dimana kita menentukan apakah beberapa bit yang digunakan berakhir pada 0 atau 1. Ini benar-benar model yang sangat bagus untuk beberapa permasalahan nyata yang muncul di aplikasi seperti pencari web dan ekstraksi informasi berdasarkan teks.
Untuk Nondeterministic Finite Automata pada text search, jika dimisalkan kita diberikan beberapa set kata, dimana kita harus memanggil keywords dan kita ingin mencari peristiwa dari beberapa kata ini. Di aplikasi seperti ini, cara yang berguna untuk memproses adalah dengan mendesain NFA, yang tidak lain sinyal, cukup masuk pada state penerimaan, yang kemudian melihat keywords. Kemudian teks pada dokumen akan memproses, mendapatkan satu karakter dalam satu waktu, lalu kemudian mengenali kejadian dari keywords yang pada teks. Ini adalah form yang simpel untuk NFA dalam mengenali beberapa kata kunci.
- Terdapat state mulai dengan transisi itu sendiri pada setiap input simbol, seperti contoh, setiap printable karakter ASCII jika kita periksa maka secara intuitif, state mulai akan menampilkan “perkiraan” yang belum pasti memperlihatkan satu dari kata tersebut, meskipun kita melihat beberapa salah satu kata dari kelimat yang ada.
- Untuk setiap keyword a1,a2…ak, terdapat k state, mari dikatakan sebagai q1, q2…qk. Terdapat transisi dari state mulai ke q1 berdasarkan simbol a1, transisi dari q1 ke q2 berdasarkan simbol a2, dan seterusnya. Untuk state qk meruapakan state penerimaan dan mengarahkan / menunjukkan bahwa keyword a1,a2…ak telah ditemukan.
Contoh DFA :
Seperti yang kita ketahui, sebagai aturan DFA, kita hanya bisa berada di satu state dalam satu waktu.
Jika dimisalkan kita ingin mendesain DFA untuk mengenali kejadian dari kata web dan ebay. Di sini, simbol “ ∑ ” adalah singkatan dari set input yang semua karakter ASCII yang dapat dicetak termasuk w, e, b, a, y. 0 adalah keadaan awal kita, artinya kita tidak memiliki apa pun yang kita mau. State 1 mengatakan bahwa kita memiliki "w". State 2 mengatakan bahwa kita memiliki "w" diikuti oleh "e" (we). State 3 memberi tahu kita memiliki "web", state ini adalah state yang diterima. State 4 mengatakan bahwa kita memiliki "e". State 5 mengatakan bahwa kita memiliki "eb". State 6 mengatakan bahwa kita memiliki "eba". State 7 mengatakan bahwa kita memiliki "ebay", ini juga merupakan state yang diterima.
Contoh NFA :
Seperti yang kita ketahui, sebagai aturan NFA, kita bisa berada di beberapa state pada waktu tertentu.
Jika dimisalkan kita ingin mendesain NFA untuk mengenali kejadian dari kata web dan ebay. Diagram transisi untuk NFA didesain menggunakan aturan pada gambar dibawah. State 1 adalah state mulai (permulaan), dan kita menggunakan (∑) yang berdiri sebagai set dari semua printable karakter ASCII. State 2 sampai 4 bertanggung jawab untuk mengenali web, sedangkan state 5 sampai 8 bertanggung jawab untuk mengenali ebay.