Eliminasi useless symbol di 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 useless symbol. Tiga hal yang umum terjadi yang membuat suatu grammar dikatakan useless adalah jika tidak pernah bisa dipanggil (unreachable) selama melakukan derivasi, tidak ada aturan pemproduksinya, atau berulang sehingga tidak dapat berhenti.

Perhatikan contoh CFG berikut ini.

S -> aSA | aBB | Aa | aD

A -> aA | aa | DA

B -> aBB | aB | bB

C -> c

1. Unreachable production
   Bila kita Analisa CFG diatas, maka dapat dilihat bahwa ada unit produksi C namun C tidak pernah dipanggil. Pada awalnya kita selalu melakukan derivasi mulai dari start symbol. Dari symbol S memiliki beberapa aturan namun aturan tersebut juga tidak ada yang memanggil C secara langsung. Oleh karena itu kita akan cek kembali apakah C bisa dipanggil dari variabel yang lain. Dari unit produksi A hanya akan memanggil variabel A dan D lagi, namun masih tidak ada C, demikian juga pada unit B, sehingga C kita nyatakan sebagai useless symbol.

   Hasil eliminasi unit C:

   S -> aSA | aBB | Aa | aD
   A -> aA | aa | DA
   B -> aBB | aB | bB

2. Tidak ada unit produksi
   Setelah kita menghilangkan unreachable code, kita bisa menganalisa kembali apakah ada hal lainnya yang bisa dihilangkan. Contoh dari tidak ada unit produksi disini adalah variabel D. Dari Start symbol S memiliki beberapa aturan yang salah satunya adalah S à aD, akan tetapi dari CFG yang dimiliki tidak ada aturan grammar untuk produksi D, sehingga kita bisa menghapus semua aturan produksi yang mengandung unit D. Hasil dari eliminasi aturan yang mengandung unit D adalah sebagai berikut.

   S -> aSA | aBB | Aa
   A -> aA | aa
   B -> aBB | aB | bB

3. Perulangan
   Dari grammar yang dihasilkan setelah tahap nomor 2 diatas maka kita akan menganalisa lebih lanjut apakah masih ada useless symbol. Untuk saat ini kita akan coba mencari apakah ada perulangan yang tidak dapat dihentikan pada CFG tersebut. Perhatikan unit produksi B yang mempunyai 3 aturan aBB | aB| bB. Terlihat jelas disini bahwa terdapat perulangan (memanggil dirinya sendiri) namun perlu dianalisa apakah perulangan ini dapat dihentikan atau tidak. Sebuah perulangan (derivasi dari sebuah unit) dapat dihentikan ketika menemukan terminal symbol. Andaikata derivasi kita dari start symbol mencapai derivasi B maka derviasi B hanya mempunyai 3 pilihan dimana pilihan tersebut semuanya memanggil dirinya sendiri. B akan terus diderivasi dengan memiliki ketiga aturan yang ada, dan karena tidak adanya terminal symbol pada aturan B maka perulangan tidak dapat terhenti. Oleh karena itu unit B semuanya harus dieliminasi.

   S -> aSA | aBB | Aa
   A -> aA | aa

   Ketika kita mengeliminasi unit B maka semua aturan yang mengandung unit B juga harus dihapus.

   S -> aSA | Aa
   A -> aA | aa

   Walaupun unit produksi A memanggil dirinya sendiri (perulangan), namun karena unit produksi A memiliki aturan aa (terminal symbol) maka perulangan pada unit A dapat dihentikan.