FINITE STATE AUTOMATA dan NON FINITE STATE AUTOMATA

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 merupakan mesin otomata dari bahasa regular. Suatu Finite State Automata memiliki state yang banyaknya berhingga, dan dapat berpindah-pindah dari suatu state ke state lain. 

Secara formal finite state automata dinyatakan oleh 5 tupel atau M=(Q, Σ, δ, S, F), di mana : 
Q = himpunan state / kedudukan 
Σ = himpunan simbol input / masukan / abjad 
δ = fungsi transisi 
S = state awal / kedudukan awal (initial state) 
F = himpunan state akhir 

Finite State Automata yang memiliki tepat satu state berikutnya untuk setiap simbol masukan yang diterima disebut Deterministic Finite Automata.
Sebagai contoh, kita memiliki sebuah otomata seperti pada gambar di bawah ini.
Fungsi transisi yang ada sebagai berikut: 
d(q0 , a) = q0 
d(q0 , b) = q1 
d(q1 , a) = q1 
d(q1 , b) = q2 
d(q2 , a) = q1 
d(q2 , b) = q2

Biasanya fungsi-fungsi transisi ini kita sajikan dalam sebuah tabel transisi. Tabel transisi tersebut menunjukkan state-state berikutnya untuk kombinasi state-state dan input. Tabel transisi dari fungsi transisi di atas sebagai berikut. 

Ada dua jenis FSA :
Finite State Automata dapat berupa:
1. Deterministic Finite Autmata (DFA)
Dari suatu state ada tepat satu state berikutnya untuk setiap simbol input yang diterima.
2. NonDeterministic Finite Autmata (NDFA/NFA)
Dari suatu state bisa tedapat 0, 1 atau lebih busur keluar (transisi) berlabel simbol input yang sama.

Deterministic Finite Autmata (DFA)
Dari suatu state ada tepat satu state berikutnya untuk setiap simbol masukan yang diterima.
  • Himpunan keadaan (Q).
  • Himpunan simbol input (S)
  • Fungsi transisi (d), memuat satu keadaan asal dan satu simbol input dan satu keadaan tujuan. Keadaan awal (q0)merupakan salah satudari Q.
  • Himpunan keadaan final atau yang diterima, dinotasikan dengan F (FÍQ)
DFA terdiri atas 5 tuple, yaitu:
Q = himpunan state / kedudukan 
Σ = himpunan simbol input / masukan / abjad 
δ = fungsi transisi 
S = state awal / kedudukan awal (initial state) 
F = himpunan state akhir 
Language →L(M) : (x|∂(S,x) di dalam F)
1. Diagram Transisi / State Diagram
  • Tiap keadaan merupakan simpul
  • Tiap keadaan q Î Q dan tiap simbol a Î S, dituliskan sebagai d(q,a) = p.Artinya, diagram transisi memiliki panah dari q ke p, yang berlabel a.
  • Keadaan awal (q0) ditandai dengan adanya panah tanpa sumber.
  • Simpul yang menjadi keadaan final ditandai dengan lingkaran bergaris tepi ganda
2. Tabel Transisi
  • Representasi daftar dari suatu fungsi
  • Baris menunjukkan keadaan dan kolom menunjukkan input.
  • Isi dari baris menunjukkan keadaan q dan isi dari kolom input a menunjukkan keadaan d
dengan fungsi transisi d diberikan dalam bentuk tabel:

Finite DFA

NonDeterministic Finite Autmata (NDFA/NFA)
Non Deterministic Finite Automata didefinisikan pula dengan lima (5) tupel, sama seperti halnya pada Deterministic Finite Automata. Perhatikan contoh di bawah ini. 
Maka otomata ini disebut non-deterministik (tidak pasti arahnya). Bisa kita lihat tabel transisinya seperti di bawah ini. 

*Catatan : Perhatikan cara penulisan state hasil transisi pada tabel transisi untuk Non Deterministic Finite Automata digunakan kurung kurawal ‘{‘ dan ‘}’ karena hasil transisinya merupakan suatu himpunan state

Ekuivalensi Non-Deterministic Finite Automata ke Deterministic Finite Automata
Untuk suatu bahasa regular, kemungkinan ada sejumlah Deterministic Finite Automata yang dapat menerimanya. Perbedaannya hanyalah jumlah state yang dimiliki otomata-otomata yang saling ekuivalen tersebut. Tentu saja, dengan alasan kepraktisan, kita memilih otomata dengan jumlah state yang lebih sedikit.

Sasaran kita di sini adalah mengurangi jumlah state dari suatu Finite State Automata, dengan tidak mengurangi kemampuannya semula untuk menerima suatu bahasa.

Ada dua buah istilah baru yang perlu kita ketahui yaitu :
1. Distinguishable yang berarti dapat dibedakan.
2. Indistinguishable yang berarti tidak dapat dibedakan.

Dua DFA M1 dan M2 dinyatakan ekivalen apabila L(M1) = L(M2)

Reduksi Jumlah State pada Finite State Automata
Untuk suatu bahasa regular, kemungkinan ada sejumlah Deterministic Finite Automata yang dapat menerimanya. Perbedaannya hanyalah jumlah state yang dimiliki otomata- otomata yang saling ekuivalen tersebut. Tentu saja, dengan alasan kepraktisan, kita memilih otomata dengan jumlah state yang lebih sedikit. Sasaran kita di sini adalah mengurangi jumlah state dari suatu Finite State Automata, dengan tidak mengurangi kemampuannya semula untuk menerima suatu bahasa. Ada dua buah istilah baru yang perlu kita ketahui yaitu :
1. Distinguishable State yang berarti dapat dibedakan.
2. Indistinguishable State yang berarti tidak dapat dibedakan.

Sebagai Contoh:


Langkah-Langkahnya :
1. Identifikasilah setiap kombinasi state yang mungkin :
Kombinasi state yang mungkin adalah : (q 0 , q1 ) (q 0 , q 2 ) (q 0 , q 3 ) (q 0 , q 4 ) (q1 , q 2 ) (q1 , q 3 ) (q1 , q 4 ) (q 2 , q 3 ) (q 2 , q 4 ) (q 3 , q 4 )

2. State yang berpasangan dengan state akhir (q 4 ) merupakan state yang distinguishable
(q 0 , q1 )
(q 0 , q 2 ) 
(q 0 , q 3 ) 
(q 0 , q 4 ) : Distinguishable 
(q1 , q 2 ) 
(q1 , q 3 ) 
(q1 , q 4 ) : Distinguishable 
(q 2 , q 3 ) 
(q 2 , q 4 ) : Distinguishable 
(q 3 , q 4 ) : Distinguishable

3. Untuk pasangan state yang lain jika masing-masing state mendapat input yang sama, maka bila satu state mencapai state akhir dan yang lain tidak mencapai state akhir maka dikatakan distinguishable. 
Untuk (q 0 , q1 ) : 
δ (q0 , 1) = q3 
δ (q1 , 1) = q4 

δ (q0 , 0) = q1 
 δ (q1 , 0) = q2 Maka (q0 , q1 ) : Distinguishable 

Untuk (q0 , q 2 ) : 
δ (q0 , 1) = q3 
δ (q2 , 1) = q4

δ (q0 , 0) = q1 
δ (q2 , 0) = q1 
Maka (q0 , q2 ) : Distinguishable 

Untuk (q0 , q 3 ) : 
δ (q0 , 1) = q3 
δ (q3 , 1) = q4 

δ (q0 , 0) = q1 
δ (q3 , 0) = q2 
Maka (q0 , q3 ) : Distinguishable 

Untuk (q1 , q2 ) :
δ (q1 , 1) = q4 
δ (q 2 , 1) = q4 

δ (q1 , 0) = q2 
δ (q2 , 0) = q1 
Maka (q1 , q2 ) : Indistinguishable 

Untuk (q1 , q3 ) :
δ (q1 , 1) = q4 
δ (q3 , 1) = q4 

δ (q1 , 0) = q2 
δ (q3 , 0) = q2 
Maka (q1 , q3 ) : Indistinguishable

Untuk (q2 , q3 ) 
δ (q2 , 1) = q4 
δ (q3 , 1) = q4 

δ (q2 , 0) = q1 
δ (q3 , 0) = q2 
Maka (q2 , q3 ) : Indistinguishable

4. Maka Didapatkan pasangan state sebagai berikut : 
(q 0 , q1 ) : Distinguishable 
(q 0 , q 2 ) : Distinguishable 
(q 0 , q 3 ) : Distinguishable 
(q 0 , q 4 ) : Distinguishable 
(q1 , q 2 ) : Indistinguishable
(q1 , q 3 ) : Indistinguishable 
(q1 , q 4 ) : Distinguishable 
(q 2 , q 3 ) : Indistinguishable 
(q 2 , q 4 ) : Distinguishable 
(q 3 , q 4 ) : Distinguishable

5. Kelompokkan pasangan state yang indistinguishable : (q1 , q2 ), (q1 , q3 ), (q2 , q3 )

6. Karena q1 indistinguishable dengan q2 dan q2 indistinguishable dengan q3 , maka bisa dikatakan bahwa q1 , q2 , dan q3 saling indistinguishable dan dapat dijadikan satu state.

7. Sehingga hasil penyederhanaannya adalah sebagai berikut :


Sumber:

Comments

Post a Comment