DFA Minimization menggunakan Metode Filling Table

Penulis : D4985 – Novita Hanafiah, S.Kom.,M.Sc.

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 yang kedua yaitu filling table.

Simulasi metode filling table tersebut akan diperlihatkan dengan menggunakan contoh DFA berikut ini.

Langkah pertama yang harus dilakukan adalah membuat pasangan dari state yang tidak boleh dijadikan satu state, yaitu final state dengan non-final state (final state jelas berbeda dengan non-final state). Final state yang dimiliki disini adalah I, sedangkan non-final state adalah A-H. Maka pasangan-pasangan yang dapat dibentuk adalah sebagai berikut:

A, I	D, I	H, I
B, I	E, I	G, I
C, I	F, I

Pasangan yang ada diatas menunjukan bahwa state A-H tidak boleh berada menjadi satu state, sebut saja pasangan tersebut merupakan blacklist yang kita miliki.

Langkah berikutnya adalah dengan membuat tabel yang menunjukan kombinasi pasangan yang mungkin terjadi dari state-state diatas.

Pada awalnya tanda cross akan diberikan pada cell pasangan state yang tidak dapat digabungkan menjadi satu, yaitu pasangan final state dan non-final state (dalam blacklist).

Berikutnya pengecekan akan dilakukan dimulai dari cell kiri atas ke sebelah kanan, yaitu (A, H), (A, G), (A, F), dan seterusnya. Setelah mencapai (A, B) maka akan berpindah ke cell pada baris berikutnya. Setiap kali mengujungi sebuah cell maka hal yang akan dilakukan adalah melihat fungsi transisi yang ada pada pasangan state tersebut. Jika fungsi transisi mengarah kepada state yang berada di dalam blacklist, ataupun menuju cell yang telah di cross, maka secara otomatis pasangan state tersebut juga tidak dapat di merge menjadi satu state (akan diberikan tanda cross pada cell saat ini). Namun jika ternyata pasangan state tersebut menuju pada state yang tidak berada dalam blacklist atau cell yang di cross, maka akan diberikan catatan di cell tempat ketergantungan terjadi yang kemudian dilanjutkan dengan pengecekan pada state berikutnya. Sebagai contoh mari kita bahas soal diatas.

Dimulai dari pasangan state (A,H) yang mempunyai fungsi transisi:

(A & H, 1) -> (B, I)  ; state A dengan input 1 akan menuju state B, sedangkan state H dengan input 1 akan menuju state I.

Seperti yang diketahui diawal bahwa state B dan I tidak dapat digabungkan menjadi satu karena B adalah non-final state sedangkan I adalah final state. Hal ini juga berarti bahwa state A dan state H mempunyai arah tujuan transisi yang berbeda (yang tidak dapat digabungkan menjadi satu) sehingga dengan demikian pasangan state (A, H) juga tidak dapat digabungkan. Maka kita harus memberi tanda cross pada cell pasangan (A, H).

Berikutnya cell pasangan (A, G) akan dicek fungsi transisinya.

(A & G, 1) -> (B, I); state A dengan input 1 akan menuju state B, sedangkan state G dengan input 1 akan menuju state I. (B, I) berada dalam blacklist, maka pasangan (A, G) tidak dapat dimerge menjadi satu.

(A & F, 1) -> (B, I); sama dengan pasangan (A, H) dan (A, G) dimana state (A, F) tidak dapat digabung.

Berikutnya state (A & E, 1) -> (B, F); state B dan F merupakan non-final state yang saat ini tidak berada pada blacklist. Jika demikian maka perlu dicek kembali apakah cell pada pasangan (B, F) sudah di-cross atau belum. Saat ini cell (B, F) belum dicek, maka kita akan menuliskan catatan pada cell (B, F) bahwa bila cell (B, F) di cross maka berarti state (A, E) juga tidak boleh di gabungkan.

Karena state (B, F) saat ini masih memiliki kemungkinan untuk digabung, maka berikutnya dilakukan pengecekan terhadap transisi input lainnya, yaitu 2.

(A & E, 2) -> (C, G); C dan G masih merupakan non-final state dan belum ter-cross, maka masih memiliki kemungkina untuk A dan E digabungkan. Berikan catatan pada cell (C, G) bahwa bila state (C, G) di cross maka state (A, E) juga tidak bisa digabungkan. Jika seandainya state (A & E, 2) menuju ke state yang di blacklist, maka kita akan segera meng-cross pasangan state tersebut walaupun transisi input 1 tadi masih memiliki kemungkinan digabungkan.

Berikutnya kita mengecek transisi (A & E, 3) -> (D, H). Dibawah ini adalah hasil pengecekan transisi pasangan state (A, E)

Berikutnya akan dilakukan pengecekan pasangan state (A, D):

(A & D, 1) -> (B, E); (A & D, 2) -> (C, E); (A & D, 3) -> (D, E)

Berikutnya akan dilakukan pengecekan pasangan state (A, C):

(A & C, 1) -> (B, E); (A & C, 2) -> (C, E); (A & C, 3) -> (D, E)

Berikutnya akan dilakukan pengecekan pasangan state (A, B):

(A & B, 1) -> (B, E); (A & B, 2) -> (C, E); (A & B, 3) -> (D, E)

Berikutnya akan dilakukan pengecekan pasangan state (B, H), (B, G) dan (B, F):

(B & H, 1) -> (E, I); maka cell (B, H) di-cross

(B & G, 1) -> ( E, I); maka cell (B, G) di-cross

(B & F, 1) -> (E, I); maka cell (B, F) di-cross, dank arena di cell (B, F) ada catatan ketergantungan dari state (A, E) maka cell pasangan (A, E) juga akan di-cross.

Berikutnya akan dilakukan pengecekan pasangan state (B, E), (B, D), (B, C), (C, H), (C, G), (C, F), (C, E) dan (C, D):

(B & E, 1) -> (E, F); (B & E, 2) -> (E, G); (B & E, 3) -> (E, H)

(B & D, 1) -> (E, E); (B & D, 2) -> (E, E); (B & D, 3) -> (E, E)

(B & C, 1) -> (E, E); (B & C, 2) -> (E, E); (B & C, 3) -> (E, E)

(C & H, 1) -> (E, I); maka cell (C, H) di-cross.

(C & G, 1) -> (E, I); maka cell (C, G) akan di-cross dan karena di cell tersebut ada ketergantungan maka backtrack kembali untuk mengecek apakah cell (A, E) tersebut sudah di-cross atau belum.

(C & F, 1) -> ( E, I); maka cell (C, F) akan di-cross

(C & E, 1) -> (E, F); (C & E, 2) -> (E, G); (C & E, 3) -> (E, H);

(C & D, 1) -> (E,E); (C & D, 2) -> (E,E); (C & D, 3) -> (E,E)

Berikutnya akan dicek pasangan state berikutnya (D, H), (D, G), (D, F), (D, E):

(D & H, 1) -> (E, I); maka cell akan di-cross

(D & G, 1) -> (E, I); maka cell akan di-cross

(D & F, 1) -> (E, I); maka cell akan di-cross

(D & E, 1) -> (E, F); (D & E, 2) -> (E, G); (D & E, 3) -> (E, H);

Untuk selanjutnya pengecekan terhadap pasangan state (E, H):

 (E & H, 1) -> (G, I); maka cell akan di-cross dan seluruh pasangan state yang tergantung pada state ini akan di-cross, yaitu (B,E), (C,E) dan (D,E). Ketika cell (B, E) di-cross maka ketergantungan pada cell ini juga di-cross, yaitu (A,D), (A,C), dan (A, B)

Berikutnya pasangan state (E, G), (E, F), (F, H), (F, G), dan (G, H):

(E & G, 1) -> (F, I); maka cell akan di cross dan semua ketergantungannya.

(E & F, 1) -> (F, I); maka cell akan di cross dan semua ketergantungannya.

(F & H, 1) -> (I, I); (F & H, 2) -> ( I, -); maka cell akan di-cross

(F & G, 1) -> (I, I); (F & G, 2) -> (I, I); (F & G, 3) -> (I, I); cell memiliki kemungkinan untuk digabungkan

(G & H, 1) -> (I, I); (G & H, 2) -> (I, -); maka cell akan di-cross

Setelah semua pasangan state sudah dikunjungi maka hasil akhirnya seperti yang dilihat pada tabel diatas adalah pasangan state (B,D), (B,C), (C,D) dapat digabungkan menjadi satu state, dan pasangan state (F,G) dapat digabungkan menjadi satu state juga.