Penerapan Finite State Automata
Finite State Automata/state otomata berhingga, selanjutnya kita sebut sebagai FSA, bukanlah mesin fisik tetapi suatu model matematika dari suatu sistem yang menerima input dan output diskrit. Finite state automata memiliki state ke state lain. Perubahan state ini dinyatakan oleh fungsi transisi. Jenis otomata ini tidak memiliki tempat penyimpanan sehingga kemampuan ‘mengingatnya’ terbatas. Mekanisme kontrol pada suatu elevator / lift adalah contoh yang bagus untuk suatu otomata.
Mekanisme tersebut tidak ‘mengingat’ semua permintaan sebelumnya tetapi hanya posisi lift saat itu pada suatu lantai, pergerakan (keatas atau bawah). Dan sekumpulan permintaan yang belum terpenuhi. Dalam ilmu komputer kita akan menemui banyak contoh dari sistem finitestate automata. teori mengenai finitestate automata adalah suatu tool yang berguna untuk merancang sistem tersebut. Mekanisme kerja suatu finitestate automata bisa diaplikasikan pada analisis leksikal, text-editor, protokol komunikasi jaringan (misal protokol kermit), dan pendek pariti.
Jenis FSA ada dua yaitu :
- Deterministic Finite Automata (DFA) : dari suatu state ada tepat satu state berikutnya untuk setiap simbol masukan yang diterima.
- Non-deterministic Finite Automata (NFA) : dari suatu state ada 0, 1 atau lebih state berikutnya untuk setiap simbol masukan yang diterima.
Contoh : pengujian parity ganjil.
Misal input : 1101 ; Genap 1 Ganjil 1 Genap 0 Genap 1 Ganjil diterima mesin
Misal input : 1100 ; Genap 1 Ganjil 1 Genap 0 Genap 0 Genap ditolak mesin
Finite State Automata dinyatakan oleh 5 tuple,
M=(Q , Σ , δ , S , F )
Q = himpunan state
Σ = himpunan simbol input
δ = fungsi transisi
δ : Q × Σ S ∈ Q S = state awal / initial state
F = state akhir, F ⊆ Q
Deterministic Finite AutomataPada Otomata Berhingga Deterministik/Deterministic Finite Automata, selanjutnya kita sebut sebagai DFA, dari suatu state ada tepat satu state berikutnya untuk setiap simbol masukkan yang diterima.
sumber :
https://guruinformatika.blogspot.com/2015/04/jenis-jenis-finite-state-automata-fsa.html