Misalkan terhadap 2 buah Deterministic Finite Automata, M1 dan M2, yang masing masing menerima bahasa L(M1) dan L(M2). Jika L(M1) = L(M2) maka 2 DFA tersebut dikatakan ekivalen. Sebagai contoh DFA M1 dan M2 memiliki diagram transisi seperti pada gambar 3.5 dan 3.6
Reduksi Jumlah State Pada Finite State Automata
Untuk suatu bahasa regular kemungkinan ada sejumlah DFA yang dapat menerimanya. Perbedaannya umumnya adalah pada jumlah state yang dimiliki oleh otomata-otomata yang saling ekivalen tersebut.
Tentunya secara praktis FSA dengan jumlah state yang lebih sedikit merupakan FSA yang paling efisien.
Untuk mendapatkan FSA yang efisien maka perlu dievaluasi dan direduksi jumlah state dari FSA tersebut dengan tidak mengurangi kemampuan semula dalam menerima suatu bahasa.
Setiap pasangan state didalam suatu FSA dapat dikelompokan atas :
- indistinguishable state
- distinguishable state
Indistinguishable state
indistinguishable state adalah pasangan state yang tidak dapat dibedakan. Untuk state-state yang indistinguishable pada prinsipnya dapat digabungkan menjadi satu state. Reduksi jumlah state dapat dilakukan dengan pendekatan tersebut.
Dua buah state p dan q dari sebuah FSA dikatakan indistinguishable jika : δ (q, w) F begitu pula δ (p, w) F dan δ (q, w) F begitu pula δ (p, w) F untuk semua w ∑*
Distinguishable State
Distinguishable state adalah pasangan state yang dapat dibedakan. Ini adalah kebalikan dari Indistinguishable state.
Dua buah state p dan q dari sebuah FSA dikatakan distinguishable jika ada string w ∑* sedemikian sehingga : δ (q, w) F sedangkan δ (p, w) F
Implementasi reduksi
Implementasi reduksi state dari suatu FSA dapat dilakukan sebagai berikut :
Hapuslah semua state tidak dapat dicapai dari state awal (useless state)
Indentifikasi state-state yang indistinguishable dan gabungkan Secara lebih detil tahapan-tahapanya adalah sebagai berikut :
Hapuslah semua useless state
Buatlah semua pasangan state (p, q) yang distinguishable, dimana p F - -dan q F. Catat semua pasangan-pasangan state tersebut.
5. Untuk semua state lakukan pencarian state lainnya yang distinguishable dengan aturan: “Untuk semua (p, q) dan semua a ∑, hitunglah δ (p, a) = pa dan δ (q, a) = qa . Jika pasangan (pa, qa) adalah pasangan state yang distinguishable maka pasangan (p, q) juga termasuk pasangan yang distinguishable.
6. Semua pasangan state yang tidak termasuk sebagai state yang distinguishable, adalah state-state indistinguishable.
7. Beberapa state yang indistinguishable dapat digabungkan menjadi satu state. Sesuaikan transisi dari state-state gabungan tersebut.
