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.
Bahasa yang paling sederhana adalah bahasa reguler (tipe 3). Mesin yang bisa mengenalinya adalah Finite Automata. Finite Automata adalah mesin komputasi. Pada bahasan ini mesin komputasi yang dimaksud adalah mesin abstrak bukan mesin fisik, namun memadai untuk diimplementasikan secara nyata.
Pengertian FSA
Finite Automata adalah model matematika sistem dengan masukan dan keluaran diskrit. Finite State Automata adalah model matematika yang dapat menerima inputan dan mengeluarkan output. Memiliki state berhingga banyaknya dan dapat berpindah dari satu ke yang lainnya sesuai dengan inputan dan fungsi transisi.
Contoh Sistem dengan state berhingga :
Sistem elevator
Mesin penjual minuman kaleng (vending machine)
Pengatur lampu lalu lintas
Sirkit switching di komputer dan telekomunikasi
Lexical Analyzer
Neuron Nets
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
Klasifikasi FSA
Ada dua jenis FSA :
•Deterministic finite automata (DFA)
Terdiri dari 1 transisi dari suatu state pada 1 simbol masukan.
•Non deterministik finite automata.(NFA)
Lebih dari 1 transisi dari suatu state dimungkinkan pada simbol masukan yang sama
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.
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.
Finite State Automata (FSA)
http://note-why.blogspot.com/2013/04/finite-state-automata-fsa.html
1 komentar:
serius bang agak bingung aku,,
http://guruinformatika.blogspot.com/
Post a Comment