FINITE STATE AUTOMATA

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.

Contoh nyata dari finite state automata adalah sekumpulan tombol pada console video game yang terhubung ke serangkaian tindakan tertentu di dalam game. Ketika pengguna menekan tombol tertentu, sistem tahu untuk mengimplementasikan tindakan yang sesuai.

Finite State Automata dapat didefinisikan dengan persamaan berikut:

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

Karakteristik FSA

Finite State Automata memiliki beberapa karakteristik berikut:

• Setiap Finite Automata memiliki keadaan dan transisi yang terbatas.
• Transisi dari satu keadaan ke keadaan lainnya dapat bersifat deterministik atau non-deterministik.
• Setiap Finite Automata selalu memiliki keadaan awal.
• Finite Automata dapat memiliki lebih dari satu keadaan akhir.
• Jika setelah pemrosesan seluruh string, keadaan akhir dicapai, artinya otomata menerima string tersebut.