Finite State Automata
- Bagaimana penerapan Finite State Automata ?
- Jelaskan tentang Deterministic Finite Automata !
- Jelaskan tentang Non- deterministic Finite Automata !
- Jelaskan tentang ekuivalensi antar Deterministic Finite Automata !
- Jelaskan tentang reduksi jumlah State pada Finite State Automata !
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 Automata
Pada 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
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 :
