Teknik Kompilasi : DFA MINIMIZE
Suatu Deterministic Finite Automata atau DFA dapat diubah bentuknya menjadi DFA Minimize yaitu DFA yang memiliki jumlah states yang paling minimum. Ada 2 cara untuk menentukan DFA Minimize, yaitu dengan cara menggunakan Filling Table atau dengan menggunakan cara partisi.
pada artikel ini akan dijelaskan tentang bagaimana membuat DFA Minimize dengan menggunakan cara Partisi. Untuk lebih jelasnya dapat dilihat pada contoh berikut :
Terdapat sebuah DFA yang memili 4 state yaitu {1,2,3,4}
Dimana untuk proses Partisi akan dibagi menjadi 2 grup yaitu :
- Accepting States : {4}
- Non – Accepting States : {1,2,3}
dari grup kedua yaitu {1,2,3}, akan dicari state yang dapat diminimize dengan cara melihat apakah ada state yang apabila diberikan inputan yang sama akan menuju state yang sama.
| State | a | b |
| 1 | 2 | 3 |
| 2 | 2 | 3 |
| 3 | 4 | 3 |
Dari table diatas dapat dilihat state {1} dan {2} apabila diberi inputan a akan menuju state {2} dan apabila diberi inputan b akan menuju state {3}, maka state {1} dan {2} dapat digabung sehingga bentuk DFA Minimize-nya menjadi :
Published at :