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