DFA Minimization Menggunakan Metode Partisi
Banyak produksi rancangan finite state yang dapat dihasilkan dari sebuah regular expression. DFA (Deterministic Finite Automata) merupakan salah satu finite state machine dimana hasil dari konversi sebuah NFA ke DFA atau RE ke DFA mungkin belum yang terbaik (efisien). Jumlah state yang dihasilkan tersebut dapat diminimilisasikan dengan menggunakan 2 macam metode, yaitu metode partisi (grouping) atau dengan filling table. Pada artikel ini akan dibahas cara untuk meminimalkan jumlah state pada DFA dengan menggunakan metode partisi.
Simulasi partisi akan diperlihatkan dengan menggunakan contoh DFA berikut ini.
Berikut ini adalah fungsi transisi dari DFA diatas:
Metode partisi dimulai dengan membagi seluruh state ke dalam 2 grup, yaitu grup final state dengan non-final state. Ini berarti bahwa final state dan non-final state adalah dua jenis state yang jelas berbeda, oleh karena mereka tidak dapat dijadikan ke dalam satu grup. Di sini state A sampai dengan H adalah non-final state, sedangkan sisanya I merupakan final state, sehingga kita mempunyai grup 1 yang berisi state A-H, dan grup 2 berisikan state I.
Setelah membagi seluruh state ke dalam kedua grup tersebut, maka langkah berikutnya adalah melakukan pengecekan apakah fungsi transisi dari state di setiap grup memiliki arah tujuan yang seragam. Jika state sudah memiliki arah yang sama maka tidak perlu dilakukan partisi lagi, dan ini berarti bahwa state di dalam grup yang sama tersebut dapat di-merge menjadi satu (diminimilisasikan menjadi 1 state saja). Akan tetapi jika state-state di dalam sebuah grup memiliki fungsi transisi yang berbeda maka akan dilakukan partisi kembali yaitu dengan memecahkan state yang berbeda tersebut ke dalam grup yang baru lagi. Hal ini dikarenakan kedua state tersebut memiliki fungsi transisi yang berbeda sehingga tidak dapat diminimalkan menjadi 1 state saja. Pada contoh ini dilakukan pengecekan terhadap fungsi transisi dari masing-masing state apakah menuju ke grup 1 atau ke grup 2. Berikut adalah table hasil partisi yang pertama.
Dapat dilihat bawah transisi yang ada di dalam grup 1 tidak semuanya mengarah pada grup yang sama, contohnya disini adalah transisi state F, G dan H yang mempunyai transisi berbeda dengan state A, B, C, D dan E. Oleh karena itu pada langkah berikutnya grup ini akan dipartisi kembali menjadi grup yang lebih kecil lagi dan dilakukan pengecekan kembali fungsi transisi dari setiap state ke grup yang baru dibentuk. Hasil dari partisi yang ke dua dapat dilihat pada tabel di bawah ini.
Partisi yang ke-2 menghasilkan 4 buah grup dan di dalam grup 1 terdapat state yang tidak searah fungsi transisinya, yaitu state E, sehingga kita perlu melakukan partisi lagi. Hasil dari partisi berikutnya dapat dilihat pada tabel dibawah ini.
Hasil dari partisi tabel saat ini masih memiliki grup dengan fungsi transisi yang tidak searah, yaitu state A berbeda dengan state B, C, dan D. Oleh karena itu akan dilakukan partisi kembali dan hasilnya dapat dilihat pada tabel berikut.
Setelah dilakukan partisi maka akan dilakukan pengecekan kembali untuk setiap fungsi transisi pada setiap grup tersebut. Jika semua state dalam grup sudah seragam, maka berarti partisi telah selesai dilakukan dan state yang memiliki arah yang sama (di dalam grup yang sama) berarti dapat di merge menjadi satu state saja. Contoh state B, C, dan D memiliki arah transisi yang sama, oleh karena itu dalam DFA yang baru hanya memerlukan sebuah state saja untuk menggantikan ketiga state tersebut. Berikut adalah hasil dari DFA yang telah diminimilisasikan dimana state yang awalnya berjumlah 9 menjadi 6.
