Finite State Automata (FSA)
Pengertian
FSA adalah mesin abstrak berupa model matematika dengan masukan dan keluaran diskrit serta dapat mengenal bahasa yang paling sederhana (bahasa reguler).
Mekanisme kerja Finite Automata diapalikasikan pada :
Sistem elevator, Vending Machine, Traffic Light Regulator, Protokol komunikasi, dll
Kasus FA dapat diselesaikan/digambarkan dalam 3 cara:
1.Digraph
2.Notasi Formal 5 – Tuple
3.Table State
FA-Diagraph
- Graph adalah himpunan titik dan rusuk, maka menggambar FA dengan diagraph berarti menggambarkan FA dengan titik dan rusuk berarah.
- Titik menggambarkan state, yaitu state menerima ditandai dengan lingkaran ganda dan state menoak ditandai dengan lingkaran tunggal.
- Rusuk berarah menggambarkan transisi/perpindahan, bila pada state tertentu mendapat input tertentu maka pindah ke state yang ditunjuk oleh arah rusuk berarah.
- Label menggambarkan inputan yang diberikan pada state tertentu. Rusuk berarah tanpa label menunjukan di state mana dimulai (initial state).
FA- Formal 5 Tuple
FSA didefinisikan sebagai pasangan 5 tupel :(Q, ∑, δ, S, F) atau (S, S, d, So, A), dimana :
Q / S : himpunan hingga state
∑ : himpunan hingga simbol input (alfabet)
δ / d : fungsi transisi, menggambarkan transisi state FSA akibat pembacaan simbol input. Fungsi transisi ini biasanya diberikan dalam bentuk tabel.
S / S0 : state AWAL
F / A : himpunan state AKHIR.
FA-Table State
Menggambarkan FA dengan tabel state adalah membuat matrik dari FA tersebut, dimana baris menggambarkan transisi state dengan bermacam input dan kolom menunjukan transisi state dengan sebuah input.
Contoh kalimat yang diterima FA : a, b, aa, ab, ba, aba, bab, abab, baba
Contoh kalimat yang tidak diterima FA : bb, abb, abba
FA ini menerima semua kalimat yang tersusun dari simbol a dan b yang tidak mengandung substring bb.
Nah itulah penjelasan mengenai apa itu Finite Automata, semoga materi ini dapat menjadi referensi pembelajaran kalian semua... jangan lupa tanggapan nya di kolom komentar ya guys...
0 komentar:
Post a Comment