SOAL :
1.
Tuliskan 2 jenis FSA dan jelaskan secara singkat
??
2.
Tuliskan 5 Tupel FSA dan jelaskan secara singkat
??
3.
Berikan contoh bentuk diagram transisi FSA ??
JAWABAN:
1. FSA dibedakan menjadi dua macam, yaitu :
Ø Deterministic Finite Automata (DFA).
Transisi state FSA akibat pembacaan sebuah
simbol bersifat tertentu Artinya Atomata berhingga
yang pasti (tetap/tertentu). Setiap rancangan
state input selalu tepat ada satu state
berikutnya. Dari suatu state ada tepat satu state
berikutnya untuk setiap
symbol masukan yang diterima. Untuk sebuah
state dan input yang berlaku bias ditentukan tepat satu state
berikutnya. Suatu
string x dinyatakan diterima bila_(S,x) berada pad state akhir.
Dengan kata lain secara formal bila M adalah sebuah bahasa FSA, M = (Q, _, d, S, F) menerima bahasa
yang disebut L(M) yangmerupakanhimpunan {x | d (S,x) di dalam F}.
Ø Non-Deterministik Finite Automata (NDFA).
Transisi state FSA akibat
pembacaan sebuah simbol bersifat tak tentu Artinya Atomata berhingga yang tidak pasti. Untuk setiap pasangan
state input, bias memiliki 0 (nol) atau lebih pilihan untuk
state berikutnya.
Untuk setiap
state tidak selalu tepat ada satu state
berikutnya untuk setiap simbol
input yang ada.
Dari suatu state bias terdapat
0,1 atau lebih busur keluar
(transisi) berlabel simbol input yang sama. Untuk NFA harus dicoba semua kemungkinan
yang ada sampai terdapat satu yang
mencapai state akhir.
Suatu string x dinyatakan diterima oleh bahasa
NFA, M= (Q, _, d, S, F) bila {x | d (S,x)
memuat sebuah state di dalam F}.
2.
5 Tupel FSA = Komponen M = ( Q, ∑, δ, S, F )
Ø M : Nama Mesin.
Ø Q : Himpunan hingga state/ kedudukan.
Ø ∑ : Himpunan hingga simbol input/ masukan (alfabet).
Ø Δ : Fungsi transisi, berbentuk δ
(qi, a) = qk
Ø S : State AWAL (Start) / kedudukanawal, S -> Q.
Ø F : Himpunan state AKHIR (Final), F -> Q.
3.
Contoh : FSA untuk
mengecek parity ganjil
Q ={Gnp,
Gjl}
diagram transisi
∑ = {0,1}
|
δ
|
0
|
1
|
|
Gnp
|
Gnp
|
Gjl
|
|
Gjl
|
Gjl
|
Gnp
|
tabel transisi
S = Gnp, F = {Gjl}