Finite State Automata

"Finite State Automata"

Jenis State Automata :
1.Deterministic Finite Automata (DFA)

• Otomata berhingga yang pasti (tetap/tertentu) 
• Dari suatu state ada tepat satu state berikutnya untuk setiap simbol masukan yang diterima 

2. Non-deterministic Finite Automata (NFA)

•  Dari suatu state ada 0, 1 atau lebih state berikutnya untuk setiap simbol masukan yang diterima 
•  Otomata berhingga yang tidak pasti 
•  Untuk NFA harus dicoba semua kemungkinan yang ada sampai terdapat satu yang mencapai state akhir. 

Penerapan Finite Automata
Mesin asbtrak berupa sistem model matematika dengan masukan dan keluaran diskrit yang dapat mengenali bahasa paling sederhana (bahasa reguler) dan dapat diimplementasikan secara nyata.

FSA didefinisikan sebagai pasangan 5 Tupel → M = (Q, ∑, δ, S, F).
Keterangan :
Q : Himpunan hingga state.
∑ (Sigma) : Himpunan hingga simbol input (alfabet).
δ (Delta) : Fungsi transisi, menggambarkan transisi state FSA akibat pembacaan simbol input.         
(Biasanya fungsi transisi ini digambarkan dalam bentuk tabel)

S ∈ : State awal.
F ⊆ : Himpunan state akhir.

Finite State Automata dapat dimodelkan dengan Finite State Diagram (FSD) dapat juga disebut State Transition Diagram

Lingkaran menyatakan state Lingkaran diberi label sesuai dengan nama state tersebut. Adapun pembagian lingkaran adalah:

• Lingkaran bergaris tunggal berarti state sementara 
• Lingkaran bergaris ganda berarti state akhir 

 Anak Panah menyatakan transisi yang terjadi 

• Label di anak panah menyatakan simbol yang membuat transisi dari 1 state ke state lain 
• 1 anak panah diberi label start untuk menyatakan awal mula transisi dilakukan

Contoh :

Buatlah diagram transisi dari FSA yang didefinisikan sebagai :

M = (K, VT, M, S, Z) dimana :S ={S0, S1, S2, S3}VT ={ 0,1 }K ={S0 , S3}
Dengan fungsi transisi M ada pada tabel transisi sebagai berikut :

Diagram Transisi :

Cara kerja FSA :

Mula-mula dalam state S0

Jika dari S0 menerima 1 : akan ke State-S1

Jika dari S0 menerima 11 : akan ke State-S1 lalu ke S2

Jika dari S0 menerima 0 : akan tetap di State- S0

Jika dari S0 menerima 10 : akan tetap kembali lagi State - S0

Jika dari S0 berturut-turut menerima masukan : 111, maka ia akan kembali ke- S0

Deterministic Finite Automata (FSA)

Pada DFA dari suatu state ada tepat satu state berikutnya untuk setiap simbol input (masukan) yang di terima Contoh : pengujian parity ganjil Contoh lain : Pengujian untuk menerima bit string dengan banyaknya 0 genap, serta banyaknya 1 genap.

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 Transisi :

011

δ ( q0,011)= δ ( q2,11) = δ ( q3,1)= q2

        → Ditolak

1010

δ ( q0,1010)= δ ( q1,010) = δ ( q3,10)= δ ( q2,0)= q0

        → Diterima

Non-deterministic Finite Automata (NFA) 

• Perbedaan dengan DFA: fungsi transisi dapat memiliki 0 atau lebih fungsi transisi untuk setiap simbol inputan 
• String diterima NFA bila terdapat suatu urutan transisi berdasar input, dari state awal ke state akhir
• Untuk NFA harus dicoba semua kemungkinan yang ada sampai terdapat satu yang mencapai state akhir

Contoh : 

G = ({q0 , q1 , q2 , q3, q4 }, {0,1}, δ , q0 , { q2 , q4}} 

Q = {q0 , q1 , q2 , q3, q4 } 

δ = {0,1} S = q0 

F = { q2, q4 }

Fungsi Transisi :

Contoh : String 01001 → Diterima

EKUIVALENSI NFA-DFA

Algoritma : 

1. Buat semua state yang merupakan subset dari state semula 

2. Telusuri transisi state–state yang baru terbentuk, dari diagram transisi. 

3. Tentukan state awal : {q0} 

4. Tentukan state akhir adalah state yang elemennya mengandung state akhir. 

5. Reduksi state yang tak tercapai oleh state awal. 6. Rename nama-nama state yang tersisa

Contoh :

Ubahlah NFA berikut menjadi DFA

M = {{q0,q1}, {0,1}, δ, q0,{q1}}

Q = {q0 , q1} 

δ = {0,1} 

S = q0 F = { q1 }

Tabel Transisi :

1. State yang akan dibentuk : {}, {q0} {q1},{q0,q1} 

2. Telusuri state

3. State awal : {q0} 

4. State akhir yang mengandung q1, yaitu {q1},{q0,q1}

Diagram Transisinya : 

Diket: 

M ={{q0 ,q1 ,q2 }, {0,1}, δ, q0 ,{q1 }} dengan tabel transisi sbb. Ubahlah NFA berikut menjadi DFA

Reduksi State

• Dua buah state dari FSA disebut indistinguishable (tidak dapat dibedakan)
  apabila :   δ (q,w) Є F sedangkan δ (p,w) Є F dan 
   δ (q,w) Є F sedangkan δ (p,w) Є F untuk semua w Є ∑ *

• Dua buah state dari FSA disebut distinguishable (dapat dibedakan) bila terdapat w Є ∑* sedemikian hingga: δ (q,w) Є F sedangkan δ (p,w) Є F dan δ (q,w) Є / F sedangkan δ (p,w) Є untuk semua w Є ∑ *

       δ (q,w) Є F sedangkan δ (p,w) Є F dan
       δ (q,w) Є / F sedangkan δ (p,w) Є F untuk semua w Є ∑ *

Proses Reduksi
1. Hapus semua state yang tak dapat dicapai dari state awal.
2. Catat semua pasangan state (p,q) yang distinguishable, yaitu {(p,q) | p Є F q Є F}
3. Untuk setiap pasangan (p,q) sisanya, buatlah tabel state dengan mengecek setiap pasangan satu persatu

Contoh: 

1. pasangan status indistinguishable (q1,q2), (q1,q3) dan (q2,q3). 

2. q1,q2,q3 ketiganya dapat digabung dalam satu state q123 

3. Menyesuaikan transisi, sehingga DFA menjadi

Daftar Pustaka

• https://www.slideshare.net/ahmadhaidaroh/materi-3-finite-state-automata-135546201
• http://elearning.amikompurwokerto.ac.id/index.php/download/materi/9906966406-TI037-8/2017099906966406-FSA.pdf
• http://lisetyo.staff.gunadarma.ac.id/Downloads/files/42312/TEORI+BAHASA+DAN+OTOMATA+PERTEMUAN+KE-3.pdf