Finite State Automata
Finite State Automata (FSA) 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. 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/memori sehingga 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 bekerja dengan cara membaca memori masukan berupa tape yaitu 1 karakter tiap saat (dari kiri ke kanan) menggunakan tape yang dikendalikan oleh kotak kendali finite state di mana pada mesin terdapat sejumlah finite state.
Kondisi ketika FSA membaca state awal disebut initial state. Perubahan state terjadi pada mesin ketika sebuah karakter berikutnya dibaca. Ketika head telah sampai pada akhir tape dan kondisi yang ditemui adalah state akhir, maka string yang terdapat pada tape dikatakan diterima.
Notasi matematis DFA:
– M = nama DFA
– Q = himpunan keadaan DFA
– S = himpunan alfabet
– d = fungsi transisi
– q0 = keadaan awal
– F = keadaan akhir
M = (Q, S, d, q0, F)
Contoh:
Pengujian untuk menerima bit string dengan banyaknya 0 genap, serta banyaknya 1 genap.
0011: diterima
10010: ditolak, karena banyaknya 0 ganjil
Diagram transisi-nya:
DFA-nya:
Q = {q0 , q1 , q2 , q3 }
Σ = {0,1}
S = q0
F = { q0}
fungsi transisinya adalah:
δ( q0,011)= δ( q2,11) =δ( q3,1)= q2 è Ditolak
δ( q0,1010)= δ( q1,010) =δ( q3,10)=δ( q2,0)= q0 è Diterima
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 bekerja dengan cara membaca memori masukan berupa tape yaitu 1 karakter tiap saat (dari kiri ke kanan) menggunakan tape yang dikendalikan oleh kotak kendali finite state di mana pada mesin terdapat sejumlah finite state.
Kondisi ketika FSA membaca state awal disebut initial state. Perubahan state terjadi pada mesin ketika sebuah karakter berikutnya dibaca. Ketika head telah sampai pada akhir tape dan kondisi yang ditemui adalah state akhir, maka string yang terdapat pada tape dikatakan diterima.
Jenis Finite State Automata (FSA)
a. Deterministic Finite Automata (DFA)
DFA yaitu ada setiap input, hanya ada satu keadaan (state) tujuan dari keadaan saat ini. Deterministik artinya tertentu/sudah tertentu fungsi transisinya.Notasi matematis DFA:
– M = nama DFA
– Q = himpunan keadaan DFA
– S = himpunan alfabet
– d = fungsi transisi
– q0 = keadaan awal
– F = keadaan akhir
M = (Q, S, d, q0, F)
Contoh:
Pengujian untuk menerima bit string dengan banyaknya 0 genap, serta banyaknya 1 genap.
0011: diterima
10010: ditolak, karena banyaknya 0 ganjil
Diagram transisi-nya:
DFA-nya:
Q = {q0 , q1 , q2 , q3 }
Σ = {0,1}
S = q0
F = { q0}
fungsi transisinya adalah:
δ( q0,011)= δ( q2,11) =δ( q3,1)= q2 è Ditolak
δ( q0,1010)= δ( q1,010) =δ( q3,10)=δ( q2,0)= q0 è Diterima