Nondeterministic Finite Automata (NFA)

Nama    : Petronela H. Manehat

Nim     : 11110097

Kelas   : Extention

Nondeterministic Finite Automata (NFA)

Sebuah State Diagram dari Nondeterministik Finite Automata (NFA) dan diberi input “01001”, apakah diterima atau ditolak oleh mesin (M).








Jika G diberi input “01001”, dengan state awal (q₀, 01001), maka : 
(q₀, 01001)    ├_G ({q₀, q₃}, 1001) =  d{q_0, 1} U d{q_3, 1} = {q_0, q₁} U Ø = {q_0, q₁}
 

├_G ({q_0, q₁} ,001) = d{q_0, 0} U d{q_1, 0} = {q_0, q₃} U Ø = {q_0, q₃}

├_G ({q_0, q₃} , 01) = d{q_0, 0} U d{q_3, 0} = {q_0, q₃} U {q₄}  = {q_0, q_3, q₄ }

├_G ({q_0, q_3, q₄ }, 1) = d{q_0, 1} U d{q_3, 1} U d{q_4, 1}  = {q_0, q₁} U Ø U {q₄} = {q_0, q_1, q₄ }

├_G ({q_0, q_1, q₄ })

Karena (q₀, 01001) ├*_G ({q_0, q_1, q₄ }), atau hasilnya salah satu dari F {q_2, q₄} maka diterima oleh mesin G. Jadi untuk input “01001”, diterima oleh G


Berikutnya ....


Membuat sebuah Tabel Transisi dari String "ababa" :

(q₀, ababa)   ├_M (q_1, baba)

                 ├_M (q₂ ,aba)

                 ├_M (q₃ , ba)

                 ├_M (q₂,a)

                 ├_M (q_3, e)

Selanjutnya adalah.....



Membuktikan apakah melalui mesin dibawah ini, jika diberikan input “ababaabba” apakah diterima atau ditolak???

Mari kita buktikan yach Guys....

String  “ababaabba” ......

(q₀, ababaabba)         ├_A (q_1, babaabba)

                 ├_A (q₂ , abaabba)

                 ├_A (q₃ , baabba)

                 ├_A (q₂, aabba)

                 ├_A (q_3, abba)

                 ├_A (q₁ , bba)

                 ├_A (q₂ , ba)

                 ├_A (q₄, a)

                 ├_A (q_4, e)

Karena (q₀, ababaabba) ├*_A (q₄, e), jadi “ababaabba” ditolak oleh A


Sekian dulu...