People Innovation Excellence
 

Eliminasi empty production pada CFG

Ketika kita ingin mengubah bentuk CFG yang dimiliki ke dalam bentuk CNF (Chomsky Normal Form) ataupun GNF (Greibach Normal Form), salah satu langkah yang perlu dilakukan adalah dengan menghilangkan empty production pada grammar yang dimiliki. Ketika kita melakukan eliminasi empty production ( ε ) maka kita tidak dapat langsung menghilangkan ε begitu saja, namun ada penambahan grammar juga akibat penghilangan ε tersebut.

Untuk memperjelas pemahaman maka perhatikan contoh CFG berikut ini.

S → aXbX

X → aY | bY | ε

Y → X | c

Karena ε yang mau kita hilangkan berada pada unit production X, maka kita akan melihat apakah X ada muncul di bagian RHS (Right Hand Side). Jika kita lihat di production S (S -> aXbX) maka X muncul di aturan tersebut yang berarti sebenarnya ketika derivasi dilakukan (parsing) maka X tersebut bisa kita ganti dengan memilih aY | bY | ε. Oleh karena itu ketika kita menghilangkan ε kita juga tetap mau ada kemungkinan X tersebut diderivasi menjadi ε, maka kita perlu menambah aturannya.

Untuk unit produksi S -> aXbX, pertama diandaikan bila kita melakukan derivasi X menjadi ε, maka kita akan mempunyai abX (hasil dari X yang pertama jika bernilai ε). Demikian juga X muncul setelah b, maka bila X yang ke-2 diderivasi menjadi ε kita akan mempunyai aturan aXb. Kemudian ada kemungkinan juga kedua X bernilai ε sehingga kita bisa mempunyai ab saja (dianggap X adalah ε). Maka diakhir untuk production S dapat diderivasi menjadi: S-> aXbX | abX | aXb | ab.

Setelah menambahkan aturan pada produksi S, maka kita perlu melihat kembali untuk produksi lainnya apakah ada yang mengandung X di RHS. Ternyata kita lihat bawah unit Y memiliki aturan X. Untuk kasus ini maka kita tidak perlu menambahkan aturan baru karena X hanya berdiri sendiri saja. Namun perlu diperhatikan lebih detil lagi bahwa autran produksi X juga akan memanggil Y ( X -> aY | bY) dan Y bisa memanggil  X (Y -> X), sehingga ada kemungkinan bahwa Y tersebut diderivasi menjadi ε (X -> aY -> aX -> a ε). Maka kita perlu menambahkan aturan tambahan pada unit X, sehingga menjadi X -> aY | bY | a | b.

Hasil akhir setelah menghilangkan ε adalah:

S → aXbX | abX | aXb | ab

X → aY | bY | a | b

Y → X | c


Published at :
Written By
Novita Hanafiah., S.Kom., M.Sc
Lecturer of Computer Science | School of Computer Science

Periksa Browser Anda

Check Your Browser

Situs ini tidak lagi mendukung penggunaan browser dengan teknologi tertinggal.

Apabila Anda melihat pesan ini, berarti Anda masih menggunakan browser Internet Explorer seri 8 / 7 / 6 / ...

Sebagai informasi, browser yang anda gunakan ini tidaklah aman dan tidak dapat menampilkan teknologi CSS terakhir yang dapat membuat sebuah situs tampil lebih baik. Bahkan Microsoft sebagai pembuatnya, telah merekomendasikan agar menggunakan browser yang lebih modern.

Untuk tampilan yang lebih baik, gunakan salah satu browser berikut. Download dan Install, seluruhnya gratis untuk digunakan.

We're Moving Forward.

This Site Is No Longer Supporting Out-of Date Browser.

If you are viewing this message, it means that you are currently using Internet Explorer 8 / 7 / 6 / below to access this site. FYI, it is unsafe and unable to render the latest CSS improvements. Even Microsoft, its creator, wants you to install more modern browser.

Best viewed with one of these browser instead. It is totally free.

  1. Google Chrome
  2. Mozilla Firefox
  3. Opera
  4. Internet Explorer 9
Close