Materi FSA (Finite State Automata)

 Finite State Automata 

Finite state automata adalah mesin abstrak berupa sistem model matematika dengan masukan dan keluaran diskrit yang dapat mengenali bahasa paling sederhana (bahasa reguler) dan dapat diimplementasikan secara nyata.

Finite State Automata (FSA) adalah model matematika yang dapat menerima input dan mengeluarkan output yang memiliki state yang berhingga banyaknya dan dapat berpindah dari satu state ke state lainnya berdasarkan input dan fungsi transisi. Finite state automata tidak memiliki tempat penyimpanan/memory, hanya bisa mengingat state terkini.


Finite State Automata dinyatakan oleh pasangan 5 tuple, yaitu:
M=(Q , Σ , δ , S , F )
Q = himpunan state
Σ = himpunan simbol input
δ = fungsi transisi δ : Q × Σ
S = state awal / initial state , S ∈ Q
F = state akhir, F ⊆ Q

Contoh Soal

 

jadi fungsi Fungsi Transisi soal di atas seperti ini

• Q ={ Q0,Q1,Q2,Q3,Q4}
• Σ = {0&1}
• S = {Q0}
• F = {Q1}

δ Table Transisi

 

 Contoh Hasil Tes Dari soal di atas 

1.   1101=Diterima

kita tes dengan Fast Run ,maka hasil penggambaranya seperti ini

 

Step awal di mulai dari Q0 lalu ke Q0lagi karena string yang di masukan adalah 1,selanjtnya Q1,selanjutnya Q2 dan berahir di Q1 sebagagain Final vot itu menandakan berhasil karena Final Vot kita berada di Q1 

Selanjutnya kita Uji Dengan Fitur lain Yakni Stap by state

2.    0101=DiTolak

Disini Mesin Langusung menolak karea nilai input awalanya yang di masukan bernilai 0 karena di dalam mesin ini nilai awalainya bernilai 1

Selanjutnya kita tes dengan Multiple Run

3.   1001=DiTolak

4.   0001=diTolak

1001=DiTolak karena inputan ketiganya  bernilai 0 jadi hasil runin nya dari q1 lalu menuji q2 lalu mesin tidak bisa melanjutkan , mesin akan berhenti di q2 karena input masukan selanjutnya adalah 0 

0001=diTolak karena nilai awalan bernilai 0 maka mesin akan otomatis menolak

 Selanjutnya kita uji manual Dengan string input 1110

1110=DiTerima Mulai dari State awal Q0, masuk input 1balik Ke Q0 Lalu Q0 masuk input 1 menuju Q1 kemudian Q1 masuk input 1 Ke Q3 kemudian Q3 masuk input 0 maka akan  ke Q1. Jadi apabila State akhirnya Di Q1 Itu artinya Diterima.

Terimakasih