Minimasi DFA
Minimasi DFA menggunakan Teorema Myphill-Nerode
Algoritma
Input - DFA
Output - DFA diminimalkan
Step 1- Gambarlah tabel untuk semua pasangan negara (Q i , Q j ) tidak harus terhubung langsung [Semua tidak ditandai pada awalnya]
Step 2- Pertimbangkan setiap pasangan negara bagian (Q i , Q j ) di DFA di mana Q i ∈ F dan Q j ∉ F atau sebaliknya dan tandai mereka. [Di sini F adalah himpunan keadaan akhir]
Step 3 - Ulangi langkah ini sampai kami tidak dapat menandai status lagi -
Jika ada pasangan tak bertanda (Q i , Q j ), tandai jika pasangan {δ (Q i , A), δ (Q i , A)} ditandai untuk beberapa alfabet masukan.
Step 4- Gabungkan semua pasangan tak bertanda (Q i , Q j ) dan jadikan mereka satu keadaan di DFA yang dikurangi.
Contoh
Mari kita gunakan Algoritma 2 untuk meminimalkan DFA yang ditunjukkan di bawah ini.
Step 1 - Kami menggambar tabel untuk semua pasangan negara bagian.
| Sebuah | b | c | d | e | f | |
| Sebuah | ||||||
| b | ||||||
| c | ||||||
| d | ||||||
| e | ||||||
| f |
Step 2 - Kami menandai pasangan negara bagian.
| Sebuah | b | c | d | e | f | |
| Sebuah | ||||||
| b | ||||||
| c | ✔ | ✔ | ||||
| d | ✔ | ✔ | ||||
| e | ✔ | ✔ | ||||
| f | ✔ | ✔ | ✔ |
Step 3- Kami akan mencoba menandai pasangan negara bagian, dengan tanda centang berwarna hijau, secara transitif. Jika kita memasukkan 1 untuk menyatakan 'a' dan 'f', itu akan menjadi 'c' dan 'f' masing-masing. (c, f) sudah ditandai, maka kita akan menandai pair (a, f). Sekarang, kita masukan 1 untuk menyatakan 'b' dan 'f'; itu akan menjadi 'd' dan 'f' masing-masing. (d, f) sudah ditandai, maka kita akan menandai pasangan (b, f).
| Sebuah | b | c | d | e | f | |
| Sebuah | ||||||
| b | ||||||
| c | ✔ | ✔ | ||||
| d | ✔ | ✔ | ||||
| e | ✔ | ✔ | ||||
| f | ✔ | ✔ | ✔ | ✔ | ✔ |
Setelah langkah 3, kita mendapatkan kombinasi status {a, b} {c, d} {c, e} {d, e} yang tidak bertanda.
Kita bisa menggabungkan kembali {c, d} {c, e} {d, e} menjadi {c, d, e}
Karenanya kita mendapat dua status gabungan sebagai - {a, b} dan {c, d, e}
Jadi DFA terakhir yang diminimalkan akan berisi tiga status {f}, {a, b} dan {c, d, e}
Minimasi DFA menggunakan Teorema Ekuivalensi
Jika X dan Y adalah dua kondisi dalam DFA, kita dapat menggabungkan kedua kondisi ini menjadi {X, Y} jika keduanya tidak dapat dibedakan. Dua keadaan dapat dibedakan, jika ada setidaknya satu string S, sehingga salah satu dari δ (X, S) dan δ (Y, S) menerima dan yang lain tidak menerima. Karenanya, DFA minimal jika dan hanya jika semua negara bagian dapat dibedakan.
Algoritma 3
Step 1 - Semua negara bagian Q dibagi menjadi dua partisi - final states dan non-final states dan dilambangkan dengan P0. Semua status dalam partisi adalah ekuivalen ke- 0 . Ambil counterk dan menginisialisasi dengan 0.
Step 2- Kenaikan k dengan 1. Untuk setiap partisi di P k , bagi negara bagian dalam P k menjadi dua partisi jika dapat dibedakan k. Dua status dalam partisi X dan Y ini dapat dibedakan k jika ada inputS seperti yang δ(X, S) dan δ(Y, S) adalah (k-1) -dibedakan.
Step 3- Jika P k ≠ P k-1 , ulangi Langkah 2, jika tidak lanjutkan ke Langkah 4.
Step 4- Gabungkan set ekivalen ke k dan jadikan status baru DFA yang dikurangi.
Contoh
Mari kita pertimbangkan DFA berikut -
| q | δ (q, 0) | δ (q, 1) |
|---|---|---|
| Sebuah | b | c |
| b | Sebuah | d |
| c | e | f |
| d | e | f |
| e | e | f |
| f | f | f |
Mari kita terapkan algoritma di atas ke DFA di atas -
- P 0 = {(c, d, e), (a, b, f)}
- P 1 = {(c, d, e), (a, b), (f)}
- P 2 = {(c, d, e), (a, b), (f)}
Oleh karena itu, P 1 = P 2 .
Ada tiga negara bagian dalam DFA yang dikurangi. DFA yang berkurang adalah sebagai berikut -
| Q | δ (q, 0) | δ (q, 1) |
|---|---|---|
| (a, b) | (a, b) | (c, d, e) |
| (c, d, e) | (c, d, e) | (f) |
| (f) | (f) | (f) |