Reduksi DFA[Deterministic Finite Automata]

Untuk suatu bahasa regular kemungkinanada sejumlah DFA yang dapat menerimanya

Perbedaannya umumnya adalah pada jumlahstate yang dimiliki oleh otomata-otomatayang saling ekivalen tersebut

FSA dengan jumlah state yang lebih sedikitmerupakan FSA yang paling efisien

Untuk mendapatkan FSA yang efisien makaperlu dievaluasi dan direduksi jumlah state dari FSA tersebut dengan tidak mengurangikemampuan semula dalam menerima suatubahasa

Setiap pasangan state didalam suatu FSA dapat dikelompokan atas :

Indistinguishable state

Distinguishable state Indistinguishable state adalah pasangan

state yang tidak dapat dibedakan Distinguishable state adalah pasangan state

yang dapat dibedakan Untuk state-state yang indistinguishable pada

prinsipnya dapat digabungkan menjadi satustate

Reduksi jumlah state dapat dilakukan denganpendekatan tersebut

Dua buah state p dan q dari sebuahFSA dikatakan indistinguishable jika:

δ (q, w) F begitu pula δ (p, w) Fdan

δ (q, w) F begitu pula δ (p, w) Funtuk semua

w ∑*

Dua buah state p dan q dari sebuahFSA dikatakan distinguishable jika:

ada stringw ∑*

sedemikian sehinggaδ (q, w) F sedangkan δ (p, w) F

Pasangan 2 state memiliki salah satu kemungkinan, yaitu distinguishable atau indistinguishable tetapitidak kedua-duanya

Dalam hal ini terdapat sebuah relasi: Jika p dan q indistinguishable, dan q dan r juga indistinguishablemaka p,q, dan r indistinguishable

Dalam melakukan evaluasi state, didefinisikan suaturelasi untuk Q adalah himpunan semua state, yaitu:D adalah himpunan state-state distinguishable, dimana D QN adalah himpunan state-state indistinguishable, dimana N Qmaka x N jika x Q dan x D

1. Hapuslah semua useless state2. Buatlah semua pasangan state (p, q) yang

distinguishable, dimana p F dan q F. Catatsemua pasangan-pasangan state tersebut.

3. Untuk semua state lakukan pencarian statelainnya yang distinguishable dengan aturan: “Untuk semua (p,q) dan semua a ∑, hitunglah δ(p,a)=pa dan δ(q,a)=qa . Jikapasangan (pa,qa) adalah pasangan state yang distinguishable maka pasangan (p,q) jugatermasuk pasangan yang distinguishable”

4. Semua pasangan state yang tidaktermasuk sebagai state yang distinguishable, adalah state-state indistinguishable

5. Beberapa state yang indistinguishabledapat digabungkan menjadi satu state

6. Sesuaikan transisi dari state-stategabungan tersebut. δ (q, w) F sedangkan δ (p, w) F

Lakukan reduksi state pada DFA di bawah ini !

Mencari useless state State q5 tidak dapat dicapai dari

state awal dengan jalan apapun(useless state)

Hapus state q5

Catat state-state distinguishable, yaitu: (Pisahkan state2 final dan yang bukan state2 final)q4 F sedang q0, q1, q2, q3 F

Karena q4 adalah state final dan q0, q1, q2, q3 bukan termasuk state final

Sehingga pasangan (q0,q4),(q1,q4), (q2,q4), dan (q3,q4)adalah state-state distinguishable

Cek pasangan state lain yang distinguishable, diturunkan berdasarkanpasangan dari tahapan 2 (dua), yaitu: (Selain pasangan state2 pada tahapan 2)

Untuk pasangan (q0,q1)δ(q0,0) = q1 dan δ(q1,0) = q2 (q1,q2) belum teridentifikasi dan q1,q2 Fδ(q0,1) = q3 dan δ(q1,1) = q4 (q3,q4) distinguishable maka (q0,q1) adalah distinguishable

Untuk pasangan (q0,q2)δ(q0,0) = q1 dan δ(q2,0) = q1 (q1) belumteridentifikasi dan q1 Fδ(q0,1) = q3 dan δ(q2,1) = q4 (q3,q4) distinguishable maka (q0,q2) adalah distinguishable

Untuk pasangan (q0,q3)δ(q0,0) = q1 dan δ(q3,0) = q2 (q1,q2) belum teridentifikasi dan q1, q2 Fδ(q0,1) = q3 dan δ(q3,1) = q4 (q3,q4) distinguishable maka (q0,q3) adalah distinguishable

Untuk pasangan (q1,q2)δ(q1,0) = q2 dan δ(q2,0) = q1 (q1,q2) belum teridentifikasi dan q1, q2 Fδ(q1,1) = q4 dan δ(q2,1) = q4 q4 F

maka (q1,q2) mungkin indistinguishable

Untuk pasangan (q1,q3)δ(q1,0) = q2 dan δ(q3,0) = q2 (q2) belumteridentifikasi dan q2 Fδ(q1,1) = q4 dan δ(q3,1) = q4 q4 F

maka (q1,q3) mungkin indistinguishable

Untuk pasangan (q2,q3)δ(q2,0) = q1 dan δ(q3,0) = q2 belumteridentifikasi dan q1, q2 Fδ(q2,1) = q4 dan δ(q3,1) = q4 q4 F

maka (q2,q3) mungkin indistinguishable

Karena berdasarkan relasi-relasi yang ada, tidakdapat dibuktikan (q1,q2), (q1,q3), dan(q2,q3) distinguishable, sehingga disimpulkanpasangan-pasangan state tersebutindistinguishable

Pasangan state (q1,q2), (q1,q3), dan (q2,q3) disimpulkan sebagaipasangan-pasangan state indistinguishable

Karena q1 indistinguishable denganq2, q2 indistinguishable dengan q3, maka dapat disimpulkan q1, q2, q3 saling indistinguishable dan dapatdijadikan satu state

Berdasarkan tahapan 1 s/d 5, dapatdigambarkan DFA yang sudah direduksistatenya sebagai berikut:

Lakukan reduksi state pada DFA di bawah ini !