About
Senin, 17 Maret 2014
NSFA (Nondeterministik Finite Automata)
Hay2… kali ini saya mau membagi
materi tentang NSFA (Nondeterministik Finite Automata), dimana sambungan dengan postingan sebelumnya yaitu DFSA(
(Deterministik Finite Automata). Penasaran????langsung saja di bawah ini Guys… J :
1.
Ada sebuah
Mesin G = ({q0,q1,q2,q3,q4}, {0,1}, δ,q0,{q2,q4}) dengan
dengan State diagram sbb :
 |
Pada gbr disamping bila Mesin G
diinputkan string 01001, maka
(q0,01001) ├G (q0,1001)
├G (q0,001)
├G (q3,01)
├G (q4,1)
├G (q4,e)
Karena (q0,01001)├*G (q4,e), maka string 01001ditrima oleh mesin G
2. Diketahui sebuah mesin A =
({q0,q1,q2,q3,q4}, {a,b}, δ,q0,{q0,q2,q3}) dengan dengan
State diagram sebagai berikut: :
Pada gbr di atas 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
(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 :
3. Pada Mesin No.2 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
tree path pada soal no 3 sebagai berikut :
Posting Komentar