FINITE STATE AUTOMATA



Finite 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.
FSA didefinisikan sebagai pasangan 5 tupel : (Q, ∑, δ, S, F).
Q : himpunan hingga state
∑ : himpunan hingga simbol input (alfabet)
δ : fungsi transisi, menggambarkan transisi state FSA akibat pembacaan simbol input.
(Fungsi transisi ini biasanya diberikan dalam bentuk tabel.)
S : state AWAL (Start)
F : himpunan state AKHIR (Final)



Contoh : FSA untuk mengecek parity ganjil

Description: http://i1012.photobucket.com/albums/af245/andaltria/th_otomata.jpg
Q ={Gnp, Gjl} himpunan state
∑ ={0,1} himpunan simbol input
δ = fungsi transisi,

Description: http://i1012.photobucket.com/albums/af245/andaltria/th_tabeltransisidfa.jpg

S = Gnp (Start)
F = {Gjl} (Final) himpunan state AKHIR
(ingat untuk himpunan harus ditulis di dalam {} )

dari diagram tersebut Contoh Bahasa/L(m) yang diterima adalah :
0110 (karena state akhirnya adalah finalnya state, dalam konteks ini adalah Gjl
1011 = diterima
0100 = diterima
11110 =diterima
011 = ditolak (karenan state akhirnya tidak di final state, Gnp)
11011 = ditolak

Ada dua jenis FSA :
• Deterministic finite automata (DFA)
transisi state FSA akibat pembacaan sebuah simbol bersifat tertentu.
• Non deterministik finite automata.(NFA)
transisi state FSA akibat pembacaan sebuah simbol bersifat tak tentu.
DFA (Deterministic finite automata)
Contoh DFA  
DFA :
Q = {q0, q1, q2}
δ diberikan dalam tabel berikut :
∑= {a, b}
S = q0
F = {q0, q1}
Description: tbldfa2
Description: dfa
Kalimat yang diterima oleh DFA : a, b, aa, ab, ba, aba, bab, abab, baba
Kalimat yang dittolak oleh DFA : bb, abb, abba
DFA ini menerima semua kalimat yang tersusun dari simbol a dan b yang tidak mengandung substring bb.
NFA (Non deterministik finite automata)
Contoh NFA
Berikut ini sebuah contoh NFA (Q, ∑, δ, S, F). dimana :
Q = {q0 , q1 , 21 ,q3 , q4 }
∑= {a, b,c}
S = q0
F = {q4}
Description: tabelnfa
Description: diagramnfa
kalimat yang diterima NFA di atas : aa, bb, cc, aaa, abb, bcc, cbb
kalimat yang tidak diterima NFA di atas : a, b, c, ab, ba, ac, bc
Sebuah kalimat di terima NFA jika :
• salah satu tracing-nya berakhir di state AKHIR, atau
• himpunan state setelah membaca string tersebut mengandung state AKHIR.
Kedua finite automata tersebut mampu mengenali himpunan reguler secara presisi. Dengan demikian kedua finite automata itu dapat mengenali string-string yang ditunjukkan dengan ekspresi reguler secara tepat.

 Implementasi Finite Automata
Sistem dengan state berhingga diterapkan pada:
- Sistem elevator
- Mesin pengeluar minuman kaleng (vending machine)
- Pengatur lampu lalu lintas (traffic light regulator)
- Sirkuit penyaklaran (switching) di komputer dan telekomunikasi
- Protokol komunikasi (communication protocol)
- Analisis Leksikal (Lexical analyzer)
- Neuron nets
- sistem Komputer
Finite State Diagram (FSD)
Finite State Automata dapat dimodelkan dengan Finite State Diagram (FSD) dapat juga disebut State Transition Diagram.

Finite State Diagram terdiri dari:
1. 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

2. 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
DFA dapat menuntun recognizer(pengenal) lebih cepat dibanding NDFA.
Namun demikian, DFA berukuran lebih besar dibanding NDFA yang ekivalen dengannya.
Lebih mudah membangun NDFA dibanding DFA untuk suatu bahasa, namun lebih mudah mengimplementasikan DFA diabnding NDFA.

Komentar

Postingan populer dari blog ini

MAKHLUK HIDUP DALAM EKOSISTEM ALAMI

SOFTWARE GRATIS