Finite State Automata (FSA)

• Model Matematika suatu sistem yang menerima input dan output diskrit
• Memiliki state yang banyaknya berhingga, dapat berpindah-pindah sari suatu state ke state yang lain
• Perubahan status = fungsi transisi

keterangan :

• lingkaran = state
• label lingkaran = nama state
• busur = transisi state
• label busur = simbol input
• lingkaran dengan busur tanpa label = state awal
• lingkaran ganda = state akhir / final

contoh 
input mesin : 1 1 0 1

urutan state : EVEN_ODD_EVEN_EVEN_ODD     → diterima (karena berakhir pada state akhir)

input mesin : 1 0 1

urutan state : EVEN_ODD_ODD_EVEN    → ditolak (karena tidak berakhir pada state akhir)

                               

FSA dinyatakan oleh 5 tupel atau M ( Q, ∑, δ, S, F )
Q  = himpunan state

∑  = himpunan simbol input / abjad
δ  = fungsi transisi
S = state awal, S ∈ Q
F = himpunan state akhir ,  F⊆Q


Q = { ODD,EVEN}

∑  = {0,1}
S =  EVEN
F = {ODD}

Artikel Terkait: