NSFA (Nondeterministik Finite Automata)

Assalamualaikum...
di kesempatan yang bahagia ini (karena dosen mata kuliah TBO ga masuk) hehehehe...
saya akan posting tugas tentang NSFA (Nondeterministik Finite Automata).

ternyata meskipun dosen ga masuk tetep di suruh ngerjain tugasnya hehehehe..

oke langsung aja deh..





Misalnya saya punya Mesin seperti gambar di atas , maka bisa di tulis seperti ini M = ({q0,q1,q2,q3,q4}, {0,1}, δ,q0,{q2,q4}) 
di sini kita beri nama mesinya M
Misalkan M di beri Input string 01001, maka

(q0,01001) ├M (q0,1001)
├M (q0,001)
├M (q3,01)
├M (q4,1)
├M (q4,e)
Karena (q0,01001) Berakhir di q4├*M (q4,e), maka string 01001ditrima oleh mesin M


ini adalah tree pathnya
Start dari q0----0---->q0----1---->q0-----0--->q3----0--->q4---1---->q4=finish




sekarang yang ke 2
menggunakan mesin yang ini

Sekarang saya beri nama mesinya A
Diketahui sebuah mesin A = ({q0,q1,q2,q3,q4}, {a,b}, δ,q0,{q0,q2,q3})

 bila Mesin A diinputkan string ababa, maka 

(q0,ababa) ├A (q1,baba)
├A (q2,aba)
├A (q3,ba)
├A (q2,a)
├A (q3,e)
Karena (q0,ababa)├*A (q3,e), maka string ababa diterima oleh mesin A




Tabel Transisinya seperti gambar berikut :

Tabel Transisi ini dapat mempermudah kita dalam mencari tau apakah suatu string inputan di tolak atau di terima.




Masih dengan Mesin A, Bila diinputkan string ababaabba maka :




(q0,ababaabba) ├A (q1,babaabba)
├A (q2,abaabba)
├A (q3,baabba)
├A (q2,aabba)
├A (q3,abba)
├A (q1,bba)
├A (q2,ba)
├A (q4,a)
├A (q4,e)

Karena (q0,ababa)├*A (q4,e), maka string ababa ditolak oleh mesin A 

dan ini adalah tree pathnya

sekian dulu cotoh soal tentang NSFA (Nondeterministik Finite Automata)..

wassalam...