Relasi Ekuivalensi dan Automata Minimal

Relasi Ekuivalensi dan Automata Minimal Teori Bahasa dan Automata Semester Ganjil 2013 Jum’at, 15.11.2013 Dosen pengasuh:

Kurnia Saputra ST, M.Sc Email: [email protected]

Jurusan Informatika Fakultas Matematika dan Ilmu Pengetahuan Alam Universitas Syiah Kuala FMIPA Informatika Universitas Syiah Kuala – Semester Ganjil 2013

1

Relasi Ekuivalensi (Equivalence Relations)

FMIPA Informatika Universitas Syiah Kuala – Semester Ganjil 2013

2

Teori Bahasa dan Automata

Relasi Ekuivalensi

Pengertian Relasi Ekuivalensi Definisi Relasi Sebuah relasi 𝑅 yang homogen atau unary pada himpunan 𝑀 adalah subset dari 𝑅 ⊆ 𝑀 × 𝑀. Relasi 𝑅 selain dapat ditulis dengan 𝑚1 , 𝑚2 ∈ 𝑅 dapat juga ditulis dengan 𝑚1 𝑅 𝑚2 .

Contoh Relasi: 𝑎, 𝑏 ∈ 𝑅

⟹

𝑎


𝑏

3


Relasi Ekuivalensi

Pengertian Relasi Ekuivalensi Relasi Ekuivalensi Relasi ekuivalensi 𝑅 pada himpunan 𝑀 adalah relasi dari 𝑅 ⊆ 𝑀 × 𝑀 yang memiliki properti sebagai berikut: • Relasi 𝑅 dikatakan reflexive jika (𝑎, 𝑎) ∈ 𝑅, dimana 𝑎 ∈ 𝑀. • Relasi 𝑅 dikatakan symmetric jika (𝑎, 𝑏) ∈ 𝑅 dan (𝑏, 𝑎) ∈ 𝑅. • Relasi 𝑅 dikatakan transitive jika (𝑎, 𝑏) ∈ 𝑅 dan (𝑏, 𝑐) ∈ 𝑅 dan dapat direlasikan juga dengan (𝑎, 𝑐) ∈ 𝑅.

Note: Elemen 𝑎, 𝑏 dan 𝑐 pada 𝑀 adalah sebarang.


4


Relasi Ekuivalensi

Pengertian Relasi Ekuivalensi Reflexive:

𝑎

(𝑎, 𝑎) ∈ 𝑅 Symmetric:

𝑎

𝑏

(𝑎, 𝑏) ∈ 𝑅 dan (𝑏, 𝑎) ∈ 𝑅 Transitive:

𝑎

𝑏

𝑐

(𝑎, 𝑏) ∈ 𝑅 dan (𝑏, 𝑐) ∈ 𝑅 dan (𝑎, 𝑐) ∈ 𝑅 FMIPA Informatika Universitas Syiah Kuala – Semester Ganjil 2013

5


Relasi Ekuivalensi

Kelas Ekuivalensi (Equivalence Classes)

Kelas Ekuivalensi Diketahui 𝑅 adalah relasi ekuivalensi pada himpunan 𝑀 dan 𝑚 ∈ 𝑀. Kelas ekuivalensi [𝑚]𝑅 dari 𝑚 adalah himpunan: [𝑚]𝑅 = 𝑛 ∈ 𝑀 (𝑛, 𝑚) ∈ 𝑅}

Kelas ekuivalensi di atas dapat juga ditulis dengan [𝑚] jika relasi yang dimaksud sudah jelas.


6


Relasi Ekuivalensi

Kelas Ekuivalensi (Equivalence Classes) Properti Kelas Ekuivalensi Diketahui 𝑅 adalah relasi ekuivalensi pada himpunan 𝑀 dan 𝑚 ∈ 𝑀. Maka akan berlaku kondisi: [𝑚1 ]𝑅 = [𝑚2 ]𝑅 atau [𝑚1 ]𝑅 ∩ [𝑚2 ]𝑅 = ∅ dimana untuk 𝑀 berlaku kondisi:

𝑀 = � [𝑚]𝑅 𝑚∈𝑀

Dua buah kelas ekuivalensi bisa akan sama atau bisa juga terpisah. Kedua kelas ekuivalensi terdapat di dalam himpunan 𝑀. Dengan kata lain kelas ekuivalensi adalah partisi/bagian dari himpunan 𝑀.


7


Relasi Ekuivalensi

Acceptance Equivalence

1

2

𝑏

𝑎

𝑎

𝑎

3

𝑏

4 𝑏

𝑏

𝑏

5

𝑎

6

𝑎

𝑎, 𝑏

Apakah automata di atas dapat disederhanakan?


8


Relasi Ekuivalensi


State 2 dan 3 adalah acceptance equivalence. Sama halnya pada state 4 dan 5, state-state tersebut dapat digabungkan.

1

𝑎, 𝑏 𝑎

2/3


𝑏

4/5

𝑎

6

𝑎, 𝑏

𝑏

9


Relasi Ekuivalensi


Definisi Acceptance Equivalence Diketahui sebuah DFA dengan 𝑀 = (𝑍, Σ, 𝛿, 𝑧0 , 𝐸) . Dua buah state 𝑧1 , 𝑧2 ∈ 𝑍 dikatakan acceptance equivalence jika semua word 𝑤 ∈ Σ ∗ dan kondisi berikut harus terpenuhi: 𝛿̂ 𝑧1 , 𝑤 ∈ 𝐸 ⟺ 𝛿̂ (𝑧2 , 𝑤) ∈ 𝐸


10


Relasi Ekuivalensi

Ekuivalensi Myhill-Nerode (Myhill-Nerode Equivalence)

Selain pada state, acceptance equivalence juga dapat dilakukan pada word. Hal ini dapat dilakukan dengan menggunakan ekuivalensi Myhill-Nerode.

Definisi Ekuivalensi Myhill-Nerode Diketahui sebuah bahasa 𝐿, dimana word 𝑥, 𝑦 ∈ Σ ∗ . Relasi ekuivalensi ≡𝐿 dapat didefinisikan dengan 𝑥 ≡𝐿 𝑦 if and only if (iff) untuk semua 𝑧 ∈ Σ∗ harus memenuhi kondisi (𝑥𝑥 ∈ 𝐿 ⟺ 𝑦𝑦 ∈ 𝐿)


11


Relasi Ekuivalensi

Ekuivalensi Myhill-Nerode (Myhill-Nerode Equivalence) Diketahui 𝐿 = 𝑎𝑘 𝑏𝑘 𝑘 ∈ ℕ}. Apakah kondisi di bawah ini memenuhi bahasa 𝐿 di atas? • • • •

𝑎 4 𝑏 3 ≡𝐿 𝑎 3 𝑏 2 ? 𝑎 2 𝑏 2 ≡𝐿 𝑎 3 𝑏 2 ? 𝑎 4 𝑏 2 ≡𝐿 𝑎 3 𝑏 2 ? 𝑎𝑎𝑎 ≡𝐿 𝑏𝑏𝑏𝑏 ?

Spesifikasikan kelas ekuivalensi Myhill-Nerode pada bahasa berikut ini: • 𝐿1 = 𝑤 ∈ 𝑎, 𝑏 ∗ #𝑎 𝑤 𝑔𝑔𝑔𝑔𝑔} • 𝐿1 = 𝑤 ∈ 𝑎, 𝑏, 𝑐 ∗ 𝑡𝑡𝑡𝑡𝑡 𝑏𝑏𝑏𝑏𝑏 𝑡𝑡𝑡𝑡𝑡𝑡𝑡 𝑑𝑑𝑑𝑑 𝑠𝑠𝑠𝑠𝑠𝑠𝑠 𝑎𝑎𝑎}


12


Relasi Ekuivalensi


Ekuivalensi Myhill-Nerode dan Bahasa Regular Sebuah bahasa 𝐿 ⊆ Σ ∗ dikatakan regular, iff ≡𝐿 memiliki kelas ekuivalensi berhingga/finite.


13


Relasi Ekuivalensi

Ekuivalensi Myhill-Nerode (Myhill-Nerode Equivalence) 𝐿 regular ⟹ ≡𝐿 memiliki kelas ekuivalensi berhingga/finite.

Diketahui bahasa 𝐿 dan automata 𝑀 = (𝑍, Σ, 𝛿, 𝑧0 , 𝐸) adalah DFA, dimana 𝑇 𝑀 = 𝐿. Relasi ekuivalensi ≡𝑀 didefinisikan dengan: 𝑥 ≡𝑀 𝑦 ⟺ 𝛿̂ 𝑧0 , 𝑥 = 𝛿̂ 𝑧0 , 𝑦

dimana 𝑥, 𝑦 ∈ Σ ∗

Jumlah kelas ekuivalensi ≡𝑀 sama dengan jumlah state yang mampu dicapai pada automata 𝑀, atau dapat juga disebut dengan berhingga/finite.


14


Relasi Ekuivalensi

Ekuivalensi Myhill-Nerode (Myhill-Nerode Equivalence) Selanjutnya, kita dapat membuktikan bahwa 𝑥 ≡𝑀 𝑦 akan sama dengan 𝑥 ≡𝐿 𝑦. Asumsikan 𝑥 ≡𝑀 𝑦 kemudian pilih sebarang 𝑧 ∈ Σ ∗ . Pastikan kondisi berikut ini terpenuhi: 𝑥𝑥 ∈ 𝐿 ⟺ 𝛿̂ 𝑧0 , 𝑥𝑥 ∈ 𝐸

(Definisi bahasa yang bisa diterima)

⟺ 𝛿̂ (𝛿̂ 𝑧0 , 𝑥 , 𝑧) ∈ 𝐸

(Definisi 𝛿̂ )

⟺ 𝛿̂ (𝑧0 , 𝑦𝑦) ∈ 𝐸

(Definisi 𝛿̂ )

⟺ 𝛿̂ (𝛿̂ 𝑧0 , 𝑦 , 𝑧) ∈ 𝐸

⟺ 𝑦𝑦 ∈ 𝐸

𝑥 𝑅𝑀 𝑦


Maka kondisi 𝑥 ≡𝐿 𝑦 dapat terpenuhi.

Dengan demikian, ≡𝑀 terhubung dengan semua word pada ≡𝐿 dan memiliki kelas ekuivalensi yang sama seperti ≡𝐿 . Jadi ≡𝐿 memiliki kelas ekuivalensi yang finite.


15


Relasi Ekuivalensi

Ekuivalensi Myhill-Nerode (Myhill-Nerode Equivalence) ≡𝐿 memiliki kelas ekuivalensi berhingga/finite ⟹ 𝐿 regular

Diasumsikan ≡𝐿 memiliki kelas ekuivalensi berhingga/finite. Automata finite 𝑀0 = (𝑍, Σ, 𝛿, 𝑧0 , 𝐸) untuk 𝐿 dapat dikonstruksikan, dimana definisinya adalah sebagai berikut: 𝑍=

𝑤

≡𝐿

𝑤 ∈ Σ∗ }

𝐸=

𝑤

≡𝐿

𝑤 ∈ 𝐿}

𝑧0 = [𝜀]≡𝐿 𝛿 𝑤

≡𝐿 , 𝑎

= [𝑤𝑤]≡𝐿



16


Relasi Ekuivalensi

Ekuivalensi Myhill-Nerode (Myhill-Nerode Equivalence) Dari 𝛿 𝑤

≡𝐿 , 𝑎

= [𝑤𝑤]≡𝐿 diikuti oleh 𝛿̂ 𝑤

Maka kondisinya menjadi:

𝑥 ∈ 𝐿(𝑀0 ) ⟺ 𝛿̂ [𝜀], 𝑥 ∈ 𝐸 ⟺ [𝑥] ∈ 𝐸 ⟺𝑥∈𝐸

≡𝐿 , 𝑢

= [𝑤𝑤]≡𝐿 .

(Definisi bahasa yang bisa diterima) (Definisi Final state)

Sehingga 𝑇 𝑀0 = 𝐿


17


Relasi Ekuivalensi


Dengan metode MyHill-Nerode kita dapat membuktikan sebuah bahasa regular atau tidak regular. Contoh: • Bahasa 𝐿 = 𝑎𝑘 𝑏𝑘 𝑘 ≥ 0} memiliki kelas ekuivalensi tak hingga dan tidak regular. • Bahasa 𝐿 = 𝑎𝑛 𝑏 𝑚 𝑐 𝑚 𝑛, 𝑚 ≥ 1} ∪ {𝑏 𝑚 𝑐 𝑛 | 𝑛, 𝑚 ≥ 1} memiliki kelas ekuivalensi tak hingga dan tidak regular. (Kedua bahasa di atas dapat juga dibuktikan dengan pumping lemma)


18


Relasi Ekuivalensi

Ekuivalensi Myhill-Nerode (Myhill-Nerode Equivalence) Jika diketahui 𝑀0 adalah DFA yang dikonstruksi dari kelas ekuivalensi. Untuk sebarang automata 𝑀 dimana 𝑇 𝑀 = 𝑇 𝑀0 , maka memenuhi kondisi berikut: ≡𝑀 ⊆ ≡𝐿 = ≡𝑀0

Artinya bahwa 𝑀0 bisa dikonstruksi dari 𝑀 dengan menggabungkan state kelas ekuivalensi. Dengan kata lain, 𝑀0 adalah DFA minimal dari bahasa 𝐿. Semua DFA minimal yang berasal dari satu bahasa yang sama maka DFA tersebut akan sama (walaupun dengan state yang berbeda).


19

Automata Minimal


20


Automata Minimal

Automata Minimal Bagaimana caranya untuk mengetahui bahwa sebuah DFA dikatakan minimal tanpa melakukan konstruksi kelas ekuivalensi? Solusi: Dengan cara menggabungkan state yang memiliki acceptance equivalence. Sebelum melakukan penggabungan state, hal yang pertama sekali dilakukan adalah menentukan terlebih dahulu state yang tidak acceptance equivalence (state final dan state non final), dan dilanjutkan dengan melakukan pencarian state yang non acceptance equivalence. FMIPA Informatika Universitas Syiah Kuala – Semester Ganjil 2013

21


Automata Minimal

Automata Minimal Algoritma Automata Minimal Input: DFA 𝑀 Output: Himpunan state acceptance equivalence 1. Hapus state yang tidak dapat dijangkau dari start state. 2. Buatlah tabel pasangan state {𝑧, 𝑧′}, dimana 𝑧 ≠ 𝑧′. 3. Beri tanda pasangan state 𝑧, 𝑧 ′ dimana 𝑧 ∈ 𝐸 dan 𝑧′ ∉ 𝐸. Note: 𝑧, 𝑧 ′ tidak acceptance equivalence. 4. Untuk pasangan yang tidak diberi tanda {𝑧, 𝑧′} dan dimana 𝑎 ∈ Σ, lakukan pengecekan apakah {𝛿 𝑧, 𝑎 , 𝛿(𝑧′, 𝑎)} sudah pernah diberi tanda. Jika ya, tandai {𝑧, 𝑧′}. 5. Ulangi langkah di atas sampai tidak mungkin diberi ditandai lagi. 6. Untuk pasangan {𝑧, 𝑧′} yang belum diberi tanda, berarti 𝑧 dan 𝑧′ adalah acceptance equivalence. FMIPA Informatika Universitas Syiah Kuala – Semester Ganjil 2013

22


Automata Minimal

Automata Minimal Gunakan algoritma automata minimal pada automata berikut:

2

1

𝑏 𝑎

2 𝑎 𝑎

3

𝑏

4 𝑏

𝑏

5

𝑏

𝑎

3

6

𝑎

𝑎, 𝑏

4 5 6 1

2

3

4

5

Buat tabel untuk semua pasangan state


23


Automata Minimal


2

1

𝑏 𝑎

2 𝑎 𝑎

3

𝑏

4 𝑏

𝑏

5

𝑏

𝑎 𝑎

3

6

𝑎, 𝑏

4 5 6

1

1

1

1

1

1

2

3

4

5

(1) Tandai pasangan state final dan state non final


24


Automata Minimal


2

1

𝑏 𝑎

2 𝑎 𝑎

3

𝑏

4 𝑏

𝑏

5

𝑏

𝑎 𝑎

3

6

𝑎, 𝑏

4

2

5 6

1

1

1

1

1

1

2

3

4

5

(2) Beri tanda {2, 4} karena 𝛿 2, 𝑎 = 1, 𝛿 4, 𝑎 = 6 dan {1, 6} sudah ditandai FMIPA Informatika Universitas Syiah Kuala – Semester Ganjil 2013

25


Automata Minimal


2

1

𝑏 𝑎

2 𝑎 𝑎

3

𝑏

4 𝑏

𝑏

5

𝑏

𝑎 𝑎

3

6

𝑎, 𝑏

4

2 3

5 6

1

1

1

1

1

1

2

3

4

5


26


Automata Minimal


2

1

𝑏 𝑎

2 𝑎 𝑎

3

𝑏

4 𝑏

𝑏

5

𝑏

𝑎 𝑎

3

6

𝑎, 𝑏

4

2

5

4

3

1

1

1

1

1

1

2

3

4

5

6


27


Automata Minimal


2

1

𝑏 𝑎

2 𝑎 𝑎

3

𝑏

4 𝑏

𝑏

5

𝑏

𝑎 𝑎

3

6

𝑎, 𝑏

4

2

5

5

4

3

1

1

1

1

1

1

2

3

4

5

6


28


Automata Minimal


2

1

𝑏 𝑎

2 𝑎 𝑎

3

𝑏

4 𝑏

𝑏

5

𝑏

𝑎 𝑎

3

6

𝑎, 𝑏

4

2

5

5

6

4

3

6

1

1

1

1

1

1

2

3

4

5


29


Automata Minimal


2

1

𝑏 𝑎

2 𝑎 𝑎

3

𝑏

4 𝑏

𝑏

5

𝑏

𝑎 𝑎

3

6

𝑎, 𝑏

4

7

2

5

5

6

4

3

6

1

1

1

1

1

1

2

3

4

5


30


Automata Minimal


2

1

𝑏 𝑎

2 𝑎 𝑎

3

𝑏

4 𝑏

𝑏

5

𝑏

𝑎 𝑎

6

𝑎, 𝑏

3

8

4

7

2

5

5

6

4

3

6

1

1

1

1

1

1

2

3

4

5

(8) Beri tanda {1, 3} karena 𝛿 1, 𝑏 = 2, 𝛿 3, 𝑏 = 5 dan {2, 5} sudah ditandai FMIPA Informatika Universitas Syiah Kuala – Semester Ganjil 2013

31


Automata Minimal


1

𝑏 𝑎

2 𝑎 𝑎

3

𝑏

4 𝑏

𝑏

5

𝑏

𝑎 𝑎

6

𝑎, 𝑏

2

9

3

8

4

7

2

5

5

6

4

3

6

1

1

1

1

1

1

2

3

4

5

(9) Beri tanda {1, 2} karena 𝛿 1, 𝑏 = 2, 𝛿 2, 𝑏 = 4 dan {2, 4} sudah ditandai FMIPA Informatika Universitas Syiah Kuala – Semester Ganjil 2013

32


Automata Minimal


1

𝑏 𝑎

2 𝑎 𝑎

3

𝑏

4 𝑏

𝑏

5

𝑏

𝑎 𝑎

6

𝑎, 𝑏

2

9

3

8

4

7

2

5

5

6

4

3

6

1

1

1

1

1

1

2

3

4

5

Pasangan state yang tersisa {2, 3} dan {4, 5} tidak bisa ditandai karena acceptance equivalent. FMIPA Informatika Universitas Syiah Kuala – Semester Ganjil 2013

33


Automata Minimal


1

𝑏 𝑎

1

2 𝑎 𝑎 𝑎, 𝑏 𝑎

3 2/3

𝑏

4 𝑏

𝑏

𝑏

5

𝑏

4/5

𝑎

6

𝑎 𝑎

𝑏

6

𝑎, 𝑏

𝑎, 𝑏

2

9

3

8

4

7

2

5

5

6

4

3

6

1

1

1

1

1

1

2

3

4

5

Pasangan state yang tersisa {2, 3} dan {4, 5} tidak bisa ditandai karena acceptance equivalent. FMIPA Informatika Universitas Syiah Kuala – Semester Ganjil 2013

34


Automata Minimal

Automata Minimal Hint penggunaan algoritma automata minimal: • Buatlah sebuah tabel dimana setiap pasangan state hanya ada satu. Secara vertikal 2, … , 𝑛 dan secara horizontal 1, … 𝑛 − 1. • Spesifikasikan pasangan mana yang telah diberi tanda.


35


Referensi

Referensi 1. Hopcroft, Motwani, Ullman: Introduction to Automata Theory, Languages, and Computation. Addison-Wesley, 2001 2. James A. Anderson: Automata Theory with Modern Applications, Cambridge University Press, 2006. 3. Uwe Schöning: Theoretische Informatik – kurzgefaßt. Spektrum, 2008. (5. Auflage)


36

Relasi Ekuivalensi dan Automata Minimal

Recommend Documents