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
Finite State Automata 5 Tuple
M=(Q, Ʃ,S,F, δ)
Q={q0,q1,q2,q3,q4}
Ʃ={0,1}
S=q0
F=q4
δ
|
0
|
1
|
q0
|
Q0
|
q0
|
q1
|
Q3,q4
|
Q1,q2
|
q2
|
ø
|
q1
|
q3
|
Q4
|
Q1
|
q4
|
ø
|
Q2
|
2. String Input
1.
0110 - Diterima
2.
1100 - Diterima
3.
0100 - Diterima
4.
1010 - Diterima
5.
0101 - Ditolak
1101
– Diterima oleh q0 (Initial) berputar di
q0, menuju q1, berputar di q1, berakhir q4 (Final)
0101
– Diterima oleh q0 (Initial) menuju q1,
berputar di q1, menuju q3, berakhir q4 (Final)
1001
– Diterima oleh q0 (Initial) berputar di
q0, menuju q1, menuju q3, berakhir q4 (Final)
1110
– Diterima oleh q0 (Initial) menuju q1,
menuju q3, menuju q1, berakhir q4 (Final)
0001
– Diterima oleh q0 (Initial) berputar di q0, berakhir di q0 (Bukan Final)
