Top Banner
Relasi Ekuivalensi dan Automata Minimal FMIPA Informatika Universitas Syiah Kuala – Semester Ganjil 2013 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 1
36

Relasi Ekuivalensi dan Automata MinimalΒ Β· Teori Bahasa dan Automata Relasi Ekuivalensi 𝐿 regular ≑𝐿 memiliki kelas ekuivalensi berhingga/finite. Diketahui bahasa 𝐿 dan

Jul 15, 2019

Download

Documents

ngonga
Welcome message from author
This document is posted to help you gain knowledge. Please leave a comment to let me know what you think about it! Share it to your friends and learn new things together.
Transcript
Page 1: Relasi Ekuivalensi dan Automata MinimalΒ Β· Teori Bahasa dan Automata Relasi Ekuivalensi 𝐿 regular ≑𝐿 memiliki kelas ekuivalensi berhingga/finite. Diketahui bahasa 𝐿 dan

Relasi Ekuivalensi dan Automata Minimal

FMIPA Informatika Universitas Syiah Kuala – Semester Ganjil 2013

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 1

Page 2: Relasi Ekuivalensi dan Automata MinimalΒ Β· Teori Bahasa dan Automata Relasi Ekuivalensi 𝐿 regular ≑𝐿 memiliki kelas ekuivalensi berhingga/finite. Diketahui bahasa 𝐿 dan

Relasi Ekuivalensi (Equivalence Relations)

FMIPA Informatika Universitas Syiah Kuala – Semester Ganjil 2013 2

Page 3: Relasi Ekuivalensi dan Automata MinimalΒ Β· Teori Bahasa dan Automata Relasi Ekuivalensi 𝐿 regular ≑𝐿 memiliki kelas ekuivalensi berhingga/finite. Diketahui bahasa 𝐿 dan

Pengertian Relasi Ekuivalensi

FMIPA Informatika Universitas Syiah Kuala – Semester Ganjil 2013 3

Teori Bahasa dan Automata 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:

π‘Ž, 𝑏 ∈ 𝑅 ⟹ π‘Ž 𝑏

Page 4: Relasi Ekuivalensi dan Automata MinimalΒ Β· Teori Bahasa dan Automata Relasi Ekuivalensi 𝐿 regular ≑𝐿 memiliki kelas ekuivalensi berhingga/finite. Diketahui bahasa 𝐿 dan

Pengertian Relasi Ekuivalensi

FMIPA Informatika Universitas Syiah Kuala – Semester Ganjil 2013 4

Teori Bahasa dan Automata 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.

Page 5: Relasi Ekuivalensi dan Automata MinimalΒ Β· Teori Bahasa dan Automata Relasi Ekuivalensi 𝐿 regular ≑𝐿 memiliki kelas ekuivalensi berhingga/finite. Diketahui bahasa 𝐿 dan

Pengertian Relasi Ekuivalensi

FMIPA Informatika Universitas Syiah Kuala – Semester Ganjil 2013 5

Teori Bahasa dan Automata Relasi Ekuivalensi

Reflexive: π‘Ž

π‘Ž 𝑏 Symmetric:

Transitive: π‘Ž 𝑏 𝑐

(π‘Ž, π‘Ž) ∈ 𝑅

(π‘Ž, 𝑏) ∈ 𝑅 dan (𝑏,π‘Ž) ∈ 𝑅

(π‘Ž, 𝑏) ∈ 𝑅 dan (𝑏, 𝑐) ∈ 𝑅 dan (π‘Ž, 𝑐) ∈ 𝑅

Page 6: Relasi Ekuivalensi dan Automata MinimalΒ Β· Teori Bahasa dan Automata Relasi Ekuivalensi 𝐿 regular ≑𝐿 memiliki kelas ekuivalensi berhingga/finite. Diketahui bahasa 𝐿 dan

Kelas Ekuivalensi (Equivalence Classes)

FMIPA Informatika Universitas Syiah Kuala – Semester Ganjil 2013 6

Teori Bahasa dan Automata Relasi Ekuivalensi

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.

Page 7: Relasi Ekuivalensi dan Automata MinimalΒ Β· Teori Bahasa dan Automata Relasi Ekuivalensi 𝐿 regular ≑𝐿 memiliki kelas ekuivalensi berhingga/finite. Diketahui bahasa 𝐿 dan

Kelas Ekuivalensi (Equivalence Classes)

FMIPA Informatika Universitas Syiah Kuala – Semester Ganjil 2013 7

Teori Bahasa dan Automata Relasi Ekuivalensi

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 𝑀.

Page 8: Relasi Ekuivalensi dan Automata MinimalΒ Β· Teori Bahasa dan Automata Relasi Ekuivalensi 𝐿 regular ≑𝐿 memiliki kelas ekuivalensi berhingga/finite. Diketahui bahasa 𝐿 dan

Acceptance Equivalence

FMIPA Informatika Universitas Syiah Kuala – Semester Ganjil 2013 8

Teori Bahasa dan Automata Relasi Ekuivalensi

1

2

3

4

5

6 π‘Ž

𝑏

π‘Ž

π‘Ž

𝑏

𝑏

𝑏 𝑏

π‘Ž

π‘Ž

π‘Ž, 𝑏

Apakah automata di atas dapat disederhanakan?

Page 9: Relasi Ekuivalensi dan Automata MinimalΒ Β· Teori Bahasa dan Automata Relasi Ekuivalensi 𝐿 regular ≑𝐿 memiliki kelas ekuivalensi berhingga/finite. Diketahui bahasa 𝐿 dan

Acceptance Equivalence

FMIPA Informatika Universitas Syiah Kuala – Semester Ganjil 2013 9

Teori Bahasa dan Automata Relasi Ekuivalensi

1 2/3 4/5 π‘Ž

𝑏

𝑏

π‘Ž π‘Ž, 𝑏

π‘Ž, 𝑏

6

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

Page 10: Relasi Ekuivalensi dan Automata MinimalΒ Β· Teori Bahasa dan Automata Relasi Ekuivalensi 𝐿 regular ≑𝐿 memiliki kelas ekuivalensi berhingga/finite. Diketahui bahasa 𝐿 dan

Acceptance Equivalence

FMIPA Informatika Universitas Syiah Kuala – Semester Ganjil 2013 10

Teori Bahasa dan Automata 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,𝑀) ∈ 𝐸

Page 11: Relasi Ekuivalensi dan Automata MinimalΒ Β· Teori Bahasa dan Automata Relasi Ekuivalensi 𝐿 regular ≑𝐿 memiliki kelas ekuivalensi berhingga/finite. Diketahui bahasa 𝐿 dan

Ekuivalensi Myhill-Nerode (Myhill-Nerode Equivalence)

FMIPA Informatika Universitas Syiah Kuala – Semester Ganjil 2013 11

Teori Bahasa dan Automata Relasi Ekuivalensi

Definisi Ekuivalensi Myhill-Nerode Diketahui sebuah bahasa 𝐿, dimana word π‘₯,𝑦 ∈ Ξ£βˆ—. Relasi ekuivalensi ≑𝐿 dapat didefinisikan dengan π‘₯ ≑𝐿 𝑦 if and only if (iff)

untuk semua 𝑧 ∈ Ξ£βˆ— harus memenuhi kondisi (π‘₯𝑧 ∈ 𝐿 ⟺ 𝑦𝑧 ∈ 𝐿)

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

Page 12: Relasi Ekuivalensi dan Automata MinimalΒ Β· Teori Bahasa dan Automata Relasi Ekuivalensi 𝐿 regular ≑𝐿 memiliki kelas ekuivalensi berhingga/finite. Diketahui bahasa 𝐿 dan

Ekuivalensi Myhill-Nerode (Myhill-Nerode Equivalence)

FMIPA Informatika Universitas Syiah Kuala – Semester Ganjil 2013 12

Teori Bahasa dan Automata Relasi Ekuivalensi

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 = 𝑀 ∈ π‘Ž, 𝑏, 𝑐 βˆ— π‘‘π‘‘π‘‘π‘Žπ‘˜ 𝑏𝑏𝑏𝑔𝑏 𝑑𝑔𝑑𝑑𝑑𝑑𝑑 π‘‘π‘Žπ‘‘π‘‘ 𝑠𝑠𝑏𝑀𝑏𝑑𝑑 π‘Žπ‘π‘}

Page 13: Relasi Ekuivalensi dan Automata MinimalΒ Β· Teori Bahasa dan Automata Relasi Ekuivalensi 𝐿 regular ≑𝐿 memiliki kelas ekuivalensi berhingga/finite. Diketahui bahasa 𝐿 dan

Ekuivalensi Myhill-Nerode (Myhill-Nerode Equivalence)

FMIPA Informatika Universitas Syiah Kuala – Semester Ganjil 2013 13

Teori Bahasa dan Automata Relasi Ekuivalensi

Ekuivalensi Myhill-Nerode dan Bahasa Regular Sebuah bahasa 𝐿 βŠ† Ξ£βˆ— dikatakan regular, iff ≑𝐿 memiliki kelas ekuivalensi berhingga/finite.

Page 14: Relasi Ekuivalensi dan Automata MinimalΒ Β· Teori Bahasa dan Automata Relasi Ekuivalensi 𝐿 regular ≑𝐿 memiliki kelas ekuivalensi berhingga/finite. Diketahui bahasa 𝐿 dan

Ekuivalensi Myhill-Nerode (Myhill-Nerode Equivalence)

FMIPA Informatika Universitas Syiah Kuala – Semester Ganjil 2013 14

Teori Bahasa dan Automata Relasi Ekuivalensi

𝐿 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.

Page 15: Relasi Ekuivalensi dan Automata MinimalΒ Β· Teori Bahasa dan Automata Relasi Ekuivalensi 𝐿 regular ≑𝐿 memiliki kelas ekuivalensi berhingga/finite. Diketahui bahasa 𝐿 dan

Ekuivalensi Myhill-Nerode (Myhill-Nerode Equivalence)

FMIPA Informatika Universitas Syiah Kuala – Semester Ganjil 2013 15

Teori Bahasa dan Automata Relasi Ekuivalensi

Selanjutnya, kita dapat membuktikan bahwa π‘₯ ≑𝑀 𝑦 akan sama dengan π‘₯ ≑𝐿 𝑦. Asumsikan π‘₯ ≑𝑀 𝑦 kemudian pilih sebarang 𝑧 ∈ Ξ£βˆ—. Pastikan kondisi berikut ini terpenuhi:

π‘₯𝑧 ∈ 𝐿 ⟺ οΏ½Μ‚οΏ½ 𝑧0, π‘₯𝑧 ∈ 𝐸

⟺ 𝛿(οΏ½Μ‚οΏ½ 𝑧0, π‘₯ , 𝑧) ∈ 𝐸

⟺ 𝛿(𝑧0,𝑦𝑧) ∈ 𝐸

⟺ οΏ½Μ‚οΏ½(οΏ½Μ‚οΏ½ 𝑧0,𝑦 , 𝑧) ∈ 𝐸

⟺ 𝑦𝑧 ∈ 𝐸

(Definisi bahasa yang bisa diterima)

(Definisi 𝛿)

π‘₯ 𝑅𝑀 𝑦

(Definisi 𝛿)

(Definisi bahasa yang bisa diterima)

Maka kondisi π‘₯ ≑𝐿 𝑦 dapat terpenuhi. Dengan demikian, ≑𝑀 terhubung dengan semua word pada ≑𝐿 dan memiliki kelas ekuivalensi yang sama seperti ≑𝐿. Jadi ≑𝐿 memiliki kelas ekuivalensi yang finite.

Page 16: Relasi Ekuivalensi dan Automata MinimalΒ Β· Teori Bahasa dan Automata Relasi Ekuivalensi 𝐿 regular ≑𝐿 memiliki kelas ekuivalensi berhingga/finite. Diketahui bahasa 𝐿 dan

Ekuivalensi Myhill-Nerode (Myhill-Nerode Equivalence)

FMIPA Informatika Universitas Syiah Kuala – Semester Ganjil 2013 16

Teori Bahasa dan Automata Relasi Ekuivalensi

≑𝐿 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 = [πœ€]≑𝐿

𝐸 = 𝑀 ≑𝐿 𝑀 ∈ 𝐿}

𝛿 𝑀 ≑𝐿 ,π‘Ž = [π‘€π‘Ž]≑𝐿

(Definisi bahasa yang bisa diterima)

Page 17: Relasi Ekuivalensi dan Automata MinimalΒ Β· Teori Bahasa dan Automata Relasi Ekuivalensi 𝐿 regular ≑𝐿 memiliki kelas ekuivalensi berhingga/finite. Diketahui bahasa 𝐿 dan

Ekuivalensi Myhill-Nerode (Myhill-Nerode Equivalence)

FMIPA Informatika Universitas Syiah Kuala – Semester Ganjil 2013 17

Teori Bahasa dan Automata Relasi Ekuivalensi

Dari 𝛿 𝑀 ≑𝐿 ,π‘Ž = [π‘€π‘Ž]≑𝐿 diikuti oleh 𝛿 𝑀 ≑𝐿 ,𝑠 = [𝑀𝑠]≑𝐿.

Maka kondisinya menjadi:

π‘₯ ∈ 𝐿(𝑀0) ⟺ 𝛿 [πœ€], π‘₯ ∈ 𝐸

⟺ [π‘₯] ∈ 𝐸

⟺ π‘₯ ∈ 𝐸

Sehingga 𝑇 𝑀0 = 𝐿

(Definisi bahasa yang bisa diterima)

(Definisi Final state)

Page 18: Relasi Ekuivalensi dan Automata MinimalΒ Β· Teori Bahasa dan Automata Relasi Ekuivalensi 𝐿 regular ≑𝐿 memiliki kelas ekuivalensi berhingga/finite. Diketahui bahasa 𝐿 dan

Ekuivalensi Myhill-Nerode (Myhill-Nerode Equivalence)

FMIPA Informatika Universitas Syiah Kuala – Semester Ganjil 2013 18

Teori Bahasa dan Automata 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)

Page 19: Relasi Ekuivalensi dan Automata MinimalΒ Β· Teori Bahasa dan Automata Relasi Ekuivalensi 𝐿 regular ≑𝐿 memiliki kelas ekuivalensi berhingga/finite. Diketahui bahasa 𝐿 dan

Ekuivalensi Myhill-Nerode (Myhill-Nerode Equivalence)

FMIPA Informatika Universitas Syiah Kuala – Semester Ganjil 2013 19

Teori Bahasa dan Automata Relasi Ekuivalensi

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).

Page 20: Relasi Ekuivalensi dan Automata MinimalΒ Β· Teori Bahasa dan Automata Relasi Ekuivalensi 𝐿 regular ≑𝐿 memiliki kelas ekuivalensi berhingga/finite. Diketahui bahasa 𝐿 dan

Automata Minimal

FMIPA Informatika Universitas Syiah Kuala – Semester Ganjil 2013 20

Page 21: Relasi Ekuivalensi dan Automata MinimalΒ Β· Teori Bahasa dan Automata Relasi Ekuivalensi 𝐿 regular ≑𝐿 memiliki kelas ekuivalensi berhingga/finite. Diketahui bahasa 𝐿 dan

Automata Minimal

FMIPA Informatika Universitas Syiah Kuala – Semester Ganjil 2013 21

Teori Bahasa dan Automata 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.

Page 22: Relasi Ekuivalensi dan Automata MinimalΒ Β· Teori Bahasa dan Automata Relasi Ekuivalensi 𝐿 regular ≑𝐿 memiliki kelas ekuivalensi berhingga/finite. Diketahui bahasa 𝐿 dan

Automata Minimal

FMIPA Informatika Universitas Syiah Kuala – Semester Ganjil 2013 22

Teori Bahasa dan Automata 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.

Page 23: Relasi Ekuivalensi dan Automata MinimalΒ Β· Teori Bahasa dan Automata Relasi Ekuivalensi 𝐿 regular ≑𝐿 memiliki kelas ekuivalensi berhingga/finite. Diketahui bahasa 𝐿 dan

Automata Minimal

FMIPA Informatika Universitas Syiah Kuala – Semester Ganjil 2013 23

Teori Bahasa dan Automata Automata Minimal

1

2

3

4

5

6 π‘Ž

𝑏

π‘Ž

π‘Ž

𝑏

𝑏

𝑏 𝑏

π‘Ž

π‘Ž

π‘Ž, 𝑏

Gunakan algoritma automata minimal pada automata berikut:

Buat tabel untuk semua pasangan state

2

3

4

5

6 1 2 3 4 5

Page 24: Relasi Ekuivalensi dan Automata MinimalΒ Β· Teori Bahasa dan Automata Relasi Ekuivalensi 𝐿 regular ≑𝐿 memiliki kelas ekuivalensi berhingga/finite. Diketahui bahasa 𝐿 dan

Automata Minimal

FMIPA Informatika Universitas Syiah Kuala – Semester Ganjil 2013 24

Teori Bahasa dan Automata Automata Minimal

1

2

3

4

5

6 π‘Ž

𝑏

π‘Ž

π‘Ž

𝑏

𝑏

𝑏 𝑏

π‘Ž

π‘Ž

π‘Ž, 𝑏

Gunakan algoritma automata minimal pada automata berikut:

(1) Tandai pasangan state final dan state non final

2

3

4

5

6 1 2 3 4 5

1 1 1 1 1

Page 25: Relasi Ekuivalensi dan Automata MinimalΒ Β· Teori Bahasa dan Automata Relasi Ekuivalensi 𝐿 regular ≑𝐿 memiliki kelas ekuivalensi berhingga/finite. Diketahui bahasa 𝐿 dan

Automata Minimal

FMIPA Informatika Universitas Syiah Kuala – Semester Ganjil 2013 25

Teori Bahasa dan Automata Automata Minimal

1

2

3

4

5

6 π‘Ž

𝑏

π‘Ž

π‘Ž

𝑏

𝑏

𝑏 𝑏

π‘Ž

π‘Ž

π‘Ž, 𝑏

Gunakan algoritma automata minimal pada automata berikut:

(2) Beri tanda {2, 4} karena 𝛿 2,π‘Ž = 1, 𝛿 4,π‘Ž = 6 dan {1, 6} sudah ditandai

2

3

4

5

6 1 2 3 4 5

1 1 1 1 1

2

Page 26: Relasi Ekuivalensi dan Automata MinimalΒ Β· Teori Bahasa dan Automata Relasi Ekuivalensi 𝐿 regular ≑𝐿 memiliki kelas ekuivalensi berhingga/finite. Diketahui bahasa 𝐿 dan

Automata Minimal

FMIPA Informatika Universitas Syiah Kuala – Semester Ganjil 2013 26

Teori Bahasa dan Automata Automata Minimal

1

2

3

4

5

6 π‘Ž

𝑏

π‘Ž

π‘Ž

𝑏

𝑏

𝑏 𝑏

π‘Ž

π‘Ž

π‘Ž, 𝑏

Gunakan algoritma automata minimal pada automata berikut:

(3) Beri tanda {3, 5} karena 𝛿 3,π‘Ž = 1, 𝛿 5,π‘Ž = 6 dan {1, 6} sudah ditandai

2

3

4

5

6 1 2 3 4 5

1 1 1 1 1

2 3

Page 27: Relasi Ekuivalensi dan Automata MinimalΒ Β· Teori Bahasa dan Automata Relasi Ekuivalensi 𝐿 regular ≑𝐿 memiliki kelas ekuivalensi berhingga/finite. Diketahui bahasa 𝐿 dan

Automata Minimal

FMIPA Informatika Universitas Syiah Kuala – Semester Ganjil 2013 27

Teori Bahasa dan Automata Automata Minimal

1

2

3

4

5

6 π‘Ž

𝑏

π‘Ž

π‘Ž

𝑏

𝑏

𝑏 𝑏

π‘Ž

π‘Ž

π‘Ž, 𝑏

Gunakan algoritma automata minimal pada automata berikut:

(4) Beri tanda {2, 5} karena 𝛿 2,π‘Ž = 1, 𝛿 5,π‘Ž = 6 dan {1, 6} sudah ditandai

2

3

4

5

6 1 2 3 4 5

1 1 1 1 1

2 3 4

Page 28: Relasi Ekuivalensi dan Automata MinimalΒ Β· Teori Bahasa dan Automata Relasi Ekuivalensi 𝐿 regular ≑𝐿 memiliki kelas ekuivalensi berhingga/finite. Diketahui bahasa 𝐿 dan

Automata Minimal

FMIPA Informatika Universitas Syiah Kuala – Semester Ganjil 2013 28

Teori Bahasa dan Automata Automata Minimal

1

2

3

4

5

6 π‘Ž

𝑏

π‘Ž

π‘Ž

𝑏

𝑏

𝑏 𝑏

π‘Ž

π‘Ž

π‘Ž, 𝑏

Gunakan algoritma automata minimal pada automata berikut:

(5) Beri tanda {3, 4} karena 𝛿 3,π‘Ž = 1, 𝛿 4,π‘Ž = 6 dan {1, 6} sudah ditandai

2

3

4

5

6 1 2 3 4 5

1 1 1 1 1

2 3 4 5

Page 29: Relasi Ekuivalensi dan Automata MinimalΒ Β· Teori Bahasa dan Automata Relasi Ekuivalensi 𝐿 regular ≑𝐿 memiliki kelas ekuivalensi berhingga/finite. Diketahui bahasa 𝐿 dan

Automata Minimal

FMIPA Informatika Universitas Syiah Kuala – Semester Ganjil 2013 29

Teori Bahasa dan Automata Automata Minimal

1

2

3

4

5

6 π‘Ž

𝑏

π‘Ž

π‘Ž

𝑏

𝑏

𝑏 𝑏

π‘Ž

π‘Ž

π‘Ž, 𝑏

Gunakan algoritma automata minimal pada automata berikut:

(6) Beri tanda {1, 5} karena 𝛿 1,π‘Ž = 3, 𝛿 5,π‘Ž = 6 dan {3, 6} sudah ditandai

2

3

4

5

6 1 2 3 4 5

1 1 1 1 1

2 3 4 5

6

Page 30: Relasi Ekuivalensi dan Automata MinimalΒ Β· Teori Bahasa dan Automata Relasi Ekuivalensi 𝐿 regular ≑𝐿 memiliki kelas ekuivalensi berhingga/finite. Diketahui bahasa 𝐿 dan

Automata Minimal

FMIPA Informatika Universitas Syiah Kuala – Semester Ganjil 2013 30

Teori Bahasa dan Automata Automata Minimal

1

2

3

4

5

6 π‘Ž

𝑏

π‘Ž

π‘Ž

𝑏

𝑏

𝑏 𝑏

π‘Ž

π‘Ž

π‘Ž, 𝑏

Gunakan algoritma automata minimal pada automata berikut:

(7) Beri tanda {1, 4} karena 𝛿 1,π‘Ž = 3, 𝛿 4,π‘Ž = 6 dan {3, 6} sudah ditandai

2

3

4

5

6 1 2 3 4 5

1 1 1 1 1

2 3 4 5

6 7

Page 31: Relasi Ekuivalensi dan Automata MinimalΒ Β· Teori Bahasa dan Automata Relasi Ekuivalensi 𝐿 regular ≑𝐿 memiliki kelas ekuivalensi berhingga/finite. Diketahui bahasa 𝐿 dan

Automata Minimal

FMIPA Informatika Universitas Syiah Kuala – Semester Ganjil 2013 31

Teori Bahasa dan Automata Automata Minimal

1

2

3

4

5

6 π‘Ž

𝑏

π‘Ž

π‘Ž

𝑏

𝑏

𝑏 𝑏

π‘Ž

π‘Ž

π‘Ž, 𝑏

Gunakan algoritma automata minimal pada automata berikut:

(8) Beri tanda {1, 3} karena 𝛿 1, 𝑏 = 2, 𝛿 3, 𝑏 = 5 dan {2, 5} sudah ditandai

2

3

4

5

6 1 2 3 4 5

1 1 1 1 1

2 3 4 5

6 7

8

Page 32: Relasi Ekuivalensi dan Automata MinimalΒ Β· Teori Bahasa dan Automata Relasi Ekuivalensi 𝐿 regular ≑𝐿 memiliki kelas ekuivalensi berhingga/finite. Diketahui bahasa 𝐿 dan

Automata Minimal

FMIPA Informatika Universitas Syiah Kuala – Semester Ganjil 2013 32

Teori Bahasa dan Automata Automata Minimal

1

2

3

4

5

6 π‘Ž

𝑏

π‘Ž

π‘Ž

𝑏

𝑏

𝑏 𝑏

π‘Ž

π‘Ž

π‘Ž, 𝑏

Gunakan algoritma automata minimal pada automata berikut:

(9) Beri tanda {1, 2} karena 𝛿 1, 𝑏 = 2, 𝛿 2, 𝑏 = 4 dan {2, 4} sudah ditandai

2

3

4

5

6 1 2 3 4 5

1 1 1 1 1

2 3 4 5

6 7

8

9

Page 33: Relasi Ekuivalensi dan Automata MinimalΒ Β· Teori Bahasa dan Automata Relasi Ekuivalensi 𝐿 regular ≑𝐿 memiliki kelas ekuivalensi berhingga/finite. Diketahui bahasa 𝐿 dan

Automata Minimal

FMIPA Informatika Universitas Syiah Kuala – Semester Ganjil 2013 33

Teori Bahasa dan Automata Automata Minimal

1

2

3

4

5

6 π‘Ž

𝑏

π‘Ž

π‘Ž

𝑏

𝑏

𝑏 𝑏

π‘Ž

π‘Ž

π‘Ž, 𝑏

Gunakan algoritma automata minimal pada automata berikut:

Pasangan state yang tersisa {2, 3} dan {4, 5} tidak bisa ditandai karena acceptance equivalent.

2

3

4

5

6 1 2 3 4 5

1 1 1 1 1

2 3 4 5

6 7

8

9

Page 34: Relasi Ekuivalensi dan Automata MinimalΒ Β· Teori Bahasa dan Automata Relasi Ekuivalensi 𝐿 regular ≑𝐿 memiliki kelas ekuivalensi berhingga/finite. Diketahui bahasa 𝐿 dan

Automata Minimal

FMIPA Informatika Universitas Syiah Kuala – Semester Ganjil 2013 34

Teori Bahasa dan Automata Automata Minimal

1

2

3

4

5

6 π‘Ž

𝑏

π‘Ž

π‘Ž

𝑏

𝑏

𝑏 𝑏

π‘Ž

π‘Ž

π‘Ž, 𝑏

Gunakan algoritma automata minimal pada automata berikut:

Pasangan state yang tersisa {2, 3} dan {4, 5} tidak bisa ditandai karena acceptance equivalent.

2

3

4

5

6 1 2 3 4 5

1 1 1 1 1

2 3 4 5

6 7

8

9

1 2/3 4/5 π‘Ž

𝑏

𝑏

π‘Ž π‘Ž, 𝑏 π‘Ž, 𝑏

6

Page 35: Relasi Ekuivalensi dan Automata MinimalΒ Β· Teori Bahasa dan Automata Relasi Ekuivalensi 𝐿 regular ≑𝐿 memiliki kelas ekuivalensi berhingga/finite. Diketahui bahasa 𝐿 dan

Automata Minimal

FMIPA Informatika Universitas Syiah Kuala – Semester Ganjil 2013 35

Teori Bahasa dan Automata 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.

Page 36: Relasi Ekuivalensi dan Automata MinimalΒ Β· Teori Bahasa dan Automata Relasi Ekuivalensi 𝐿 regular ≑𝐿 memiliki kelas ekuivalensi berhingga/finite. Diketahui bahasa 𝐿 dan

Referensi

FMIPA Informatika Universitas Syiah Kuala – Semester Ganjil 2013 36

Teori Bahasa dan Automata 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)