Equivalensi

Ekivalensi Otomata Hingga

Ekivalensi AHN menjadi AHD

Mesin Otomata Non deterministik (AHN) dapat dibuat menjadi mesin otomata Deterministik (AHD) yang ekivalen. Adapun algoritma pembentukan AHD dari AHN adalah sebagai berikut :

1. Tetapkan S(AHD) = S(AHN) & V_T(AHD) = V_T (AHN)
2. Copykan tabel AHN sbg tabel AHD, mula-mula K(AHD) = K(AHN) dan M(AHD) = M(AHN)
3. Setiap stata yang merupakan nilai dari fungsi M(AHN) namun stata tersebut bukan elemen dari K(AHN), maka tetapkan sbg elemen baru dari K(AHD). Tempatkan stata tsb pd kolom stata M(AHD). Lakukan pemetaan berdasarkan fungsi M(AHN).
4. Ulangi langkah 3 sampai tidak diperoleh stata baru
5. Z(AHD) = semua stata yang mengandung stata elemen Z(AHN).

Contoh :

Buatlah AHD yg ekivalen dengan AHN berikut :

EKIVALENSI 2 AHD

Sama halnya dengan ekivalensi AHN-e ke bentuk AHN dan ekivalensi dari AHN ke AHD; AHD,yang kemudian disebut sebagai OTOMATA ,dapat dibuat ekivalensinya sehingga mesin yang secara fisik berbeda namun sama-sama dapat menerima bahasa  [L(G)] yang sama, dapat diubah bentuknya tanpa merubah arti.

ALGORITMA :

Algoritma untuk menguji ekivalensi 2 AHD :

1.     Pastikan nama stata berbeda pada masing2 AHD

2.     Buat tabel antara pasangan terurut

            (Stata AHD A, Stata AHD A’) lengkap dgn input-inputnya

3.     Pasangan Terurut pertama diisi dgn stata awal masing2 AHD

4.     Perhatikan nilai-nilai pasangan terurut pada baris pertama, jika terdapat nilai pasangan terurut yang tidak sama, tempatkan nilai tersebut sebagai pasangan terurut baru. Dan seterusnya…

5.     Jika tidak ada lagi pasangan terurut baru, maka proses dihentikan dan kedua AHD tersebut dinyatakan ekivalen

Contoh :

Apakah Kedua AHD di bawah ini ekivalen? Buktikan !

1. Jika diketahui :

            K         = {q₀, q₁},   V_T = { a },   S = q₀,   Z = { q₁ }

            M         => (q₀, a) = q₁  (q₁, a) = q₀

            - Gambarkan grafnya

            - Tentukan bahasa yang dihasilkan, L(G)?

2. Jika diketahui :

            K         = {q₀, q₁},   V_T = { a },   S = q₀,   Z = { q₁ }

            M         => (q₀, a) = q₁  (q₁, a) = q₁

            Gambarkan grafnya & Tentukan L(G) nya