Ekuivalensi State (Ed. 1) 1/5
Lecture Notes
Uji Ekuivalensi State Deterministic Finite Automata Thompson Susabda Ngoen
Teori Bahasa dan Automata
Beberapa deterministic finite automaton (DFA) yang berbeda mungkin menyatakan sebuah language yang sama. Sebagai contoh ketiga DFA berikut menyatakan language L = {1n : n mod 3 = 0} namun jumlah state pada ketiga DFA ini berbeda. Jika kita mengimplementasikan mesin abstrak ini menjadi program tentu yang versi tiga state adalah yang paling efisien.
Gambar 1. DFA yang Menerima String dengan jumlah simbol 1 Kelipatan Tiga
A. Uji Ekuivalensi State-State Dengan String 1. Definisi State p dan state q adalah ekuivalen jika untuk semua string w, δ^(p,w) adalah accepting state jika dan hanya jika δ^(q,w) juga accepting state. Maksudnya misalkan δ^(p,w) = pa, δ^(q,w) = qa, pa dan qa adalah accepting state; atau δ^(p,w) = f, δ^(q,w) = f, dan f adalah accepting state. Hubungan dua state disebut distinguishable jika minimum terdapat sebuah string w yang menyebabkan δ^(p,w) berbeda jenis dengan δ^(q,w), maksudnya salah satunya berada di accepting state sedangkan yang lain bukan. Jika p adalah accepting state sedangkan q bukan, atau sebaliknya, maka pasangan state p dan q adalah distinguishable. 2. Table Filling Kita akan melakukan ujian ekuivalensi terhadap DFA yang paling kanan pada Gambar 1, yang mengandung tiga accepting state.
State A, D, dan G adalah final state. Berdasarkan definisi ketiga state ini berbeda dengan state-state lainnya. Pada tabel berikut simpul x digunakan untuk menyatakan distinguishable. B C D E F G
X X X
X
X X A
X X X B
X C
D
X E
X F
INSTITUT BISNIS dan INFORMATIKA INDONESIA
Ekuivalensi State (Ed. 1) 2/5
Apakah A, D, dan G ekuivalen? a. Uji dengan string 111 δ(A,111) = D δ(D,111) = G δ(G,111) = G semuanya berada di final state b. Uji dengan string 11 δ(A,11) = C δ(D,11) = F δ(G,11) = F semuanya berada di non final state ª state A, D, G adalah ekuivalen
B C D E F G
X X V X X v A
X B
B C D E F G
X X V X X V A
X X V X X B
B C D E F G
X X V X X V A
B C D E F G
X X V X X V A
X
X X X V D
X E
X F
X C
X X V D
X E
X F
X X V X X B
X X V X C
X X V D
X E
X F
X X V X X B
X X V X C
X X V D
X X E
X F
X C
Uji ekuivalensi state B 11
B D
C E
E G
F E
δ^(B,11) = D sedangkan D ekuivalen dengan G maka perlu dilakukan pengujian terhadap pasangan state (B,E). Uji dengan string 111. δ^(B,111) = E δ^(E,111) = E Keduanya berada di non-final state ª B ekuivalen dengan E
X
Uji ekuivalensi state C 1
C D
E F
F G
δ^(C,1) = D sedangkan D ekuivalen dengan G maka perlu dilakukan pengujian terhadap pasangan state (C,F). Uji dengan string 111. δ^(C,111) = F δ^(F,111) = F Keduanya berada di non-final state ª C ekuivalen dengan F Uji ekuivalensi state E 11
E G
F E
ª E distinguishable dengan F
INSTITUT BISNIS dan INFORMATIKA INDONESIA
Ekuivalensi State (Ed. 1) 3/5
State yang ekuivalen: (A,D,G), (B,E), (C,F) Dengan menyatukan state-state yang ekuivalen State baru yang mengandung label start state lama menjadi start state baru State-state baru yang mengandung label final state lama menjadi final state baru maka terbentuk DFA
B. Uji Ekuivalensi State-State Dengan Input Alphabet 1. Definisi Eliminasi semua state yang tidak bisa dijangkau dari start state. Terhadap pasangan state (p,q), jika p∈F dan q∉F atau sebaliknya, maka tandai pasangan state (p,q) sebagai distinguishable. Untuk semua pasangan state (p,q) dan semua a ∈Σ: 1. Hitung δ(p, a) = pa dan δ(q, a) = qa 2. Jika pasangan state (pa, qa) telah ditandai sebagai distinguishable maka tandai (p, q) sebagai distinguishable 2. Mark and Reduce State A, D, dan G adalah final state. Berdasarkan definisi kedua maka state-state ini distinguishable dengan state-state lain yang non-final state.
B C D E F G
X X X
A
δ(A, 1) = B dan δ(D, 1) = E (B,E) belum ada relasi sehingga (A,D) belum diketahui hubungannya. δ(A, 1) = B dan δ(G, 1) = E (B,E) belum ada relasi sehingga (A,G) belum diketahui hubungannya.
B C D E F G
X
X X
X X
X X X B
X C
X X
X
X X A
δ(B, 1) = C dan δ(C, 1) = D (C,D) sudah di-mark sebagai distinguishable (B,C) adalah distinguishable
INSTITUT BISNIS dan INFORMATIKA INDONESIA
D
X E
X F
X E
X F
X X X B
X C
D
Ekuivalensi State (Ed. 1) 4/5
δ(B, 1) = C dan δ(E, 1) = F (C,F) belum ada relasi sehingga (B,E) belum diketahui hubungannya. δ(B, 1) = C dan δ(F, 1) = G (C,G) sudah di-mark sebagai distinguishable (B,F) adalah distinguishable
δ(C, 1) = D dan δ(E, 1) = F (D,F) sudah di-mark sebagai distinguishable (C,E) adalah distinguishable
B C D E F G
X X X X A
B C D E F G
X X X X A
δ(C, 1) = D dan δ(F, 1) = G (D,G) belum ada relasi sehingga (C,F) belum diketahui hubungannya. δ(D, 1) = E dan δ(G, 1) = E Keduanya berada pada state yang sama (D,G) adalah ekuivalen
δ(E, 1) = F dan δ(F, 1) = G (F,G) sudah di-mark (E,F) adalah distinguishable δ(A, 1) = B dan δ(D, 1) = E (B,E) belum ada relasi sehingga (A,D) belum diketahui hubungannya.
B C D E F G
X X X X A
B C D E F G
X X X X A
X X X X B
X X X X B
X X X X B
X X X X B
X X X X C
X E
X F
D
X E
X F
X X V D
X E
X F
X C
X X V D
X X E
X F
X X V X C
X X V D
X X E
X F
X X X C
X X X C
X X
D
X X
δ(A, 1) = B dan δ(G, 1) = E (B,E) belum ada relasi sehingga (A,G) belum diketahui hubungannya. δ(B, 1) = C dan δ(E, 1) = F (C,F) belum ada relasi sehingga (B,E) belum diketahui hubungannya. δ(C, 1) = D dan δ(F, 1) = G (D,G) adalah ekuivalen maka (C,F) adalah ekuivalen
B C D E F G
X X X X A
INSTITUT BISNIS dan INFORMATIKA INDONESIA
X X X X B
Ekuivalensi State (Ed. 1) 5/5
δ(B, 1) = C dan δ(E, 1) = F (C,F) adalah ekuivalen maka (B,E) adalah ekuivalen
B C D E F G
X X
X X V X X B
X X V X C
X X V D
X X E
X F
A
X X V X X B
X X V X C
X X V D
X X E
X F
X X V X X V A
X X V X X B
X X V X C
X X V D
X X E
X F
X X A
δ(A, 1) = B dan δ(D, 1) = E (B,E) adalah ekuivalen maka (A,D) adalah ekuivalen
δ(A, 1) = B dan δ(G, 1) = E (B,E) adalah ekuivalen maka (A,G) adalah ekuivalen
B C D E F G
B C D E F G
X X V X X
Pasangan state yang ekuivalen: (D,G), (C,F), (B,E), (A,D), (A,G) Karena D ekuivalen dengan G, G ekuivalen dengan A maka A,D,G ekuivalen State-state baru: ADG, BE, CF Start state: ADG Final state: ADG
Referensi Hopcroft, E. John, Rajeev Motwani, Jeffrey D. Ullman, (2001), Introduction to Automata Theory, Languages, and Computation, 2nd edition, Addison-Wesley Linz, P ,(1990), An Introduction to Formal Languages and Automata, Heath
INSTITUT BISNIS dan INFORMATIKA INDONESIA
