PENYEDERHANAAN TATA BAHASA BEBAS KONTEKS (CFG)

Penyederhanaan tata bahasa bebas konteks ini memiliki tujuan agar tidak menghasilkan pohon penurunan yang memiliki kerumitan yang tidak diperlukan atau menghilangkan aturan produksiyang tidak berarti.
Langkah-langkah penyederhanaan dari tatabahasa bebas konteks ini adalah dengan cara :

1. Menghilangkan produksi yang useless (tidak berguna)
2. menghilangkan produksi unit
3. menghilangkan produksi ε 

Apa yang dumaksud dengan produksi useless, produksi unit dan produksi ε ? dan bagaimana cara menghilangkannya ? mari kita lihat pembahasannya berikut ini.



Menghilangkan Produksi Useless
Produksi Useless didefinisikan sebagai berikut :

• Poduksi yang memuat simbol variable yang tidak memiliki penurunan yang akan menghasilkan terminal-terminal seluruhnya
• Produksi yang tidak akanpernah dicapai dengan penurunan apapun dari simbol awal, sehingga produk itu redudan (berlebih)

Contoh :
Terdapat aturan produksi sebagai berikut :
S -> aBD
B -> cD | Ab
D -> ef
A -> Ed
F -> dc
 Analisa :
1) Pada aturan produksi A -> Ed, E tidak memiliki penurunan. sehingga dapat dihilangkan
2) Aturan produksi F -> dc, redudan. sehingga aturan produksi tersebut dapat dihilangkan
Sisa aturan produksi yang telah disederhanakan adalah sebagai berikut :
S -> aBD
B -> cD | Ab
D -> ef

Analisa kembali :
aturan produksi B -> Ab, A tidak memiliki penurunan. sehingga didapat penyederhanaan lagi menjadi 
S -> aBD
B-> cD
D -> ef
Kesimpulannya adalah bahwa produk useless yang dihilangkan adalah :
A-> Ed
F -> dc
B-> Ab


Menghilangkan Produksi Unit
Produksi Unit adalah produksi dimana ruas kiri dan kanan aturan produksi hanya berupa satu simbol variabel. Contoh : A -> B, C -> D
keberadaan produksi unit ini membuat tata bahasa memiliki kerumitan yang tak perlu. untuk menyederhanakan produksi unit, dilakukan penggantian aturan produksi unit tersebut.

Contoh :
diberikan aturan produksi sebagai berikut :
S -> A
S -> Aa
A -> B
B -> C
B -> b
C -> D
C -> ab
D -> b
Lakukan penggantian berurutan mulai dari aturan produksi yang paling dekat menuju ke penurunan terminal-terminal (" =>" dibaca "menjadi")
C -> D => C -> b
B -> C => B -> b | ab, karena B -> b sudah ada maka cukup dituliskan B -> ab
A -> B => A -> ab | b
S -> A => S -> ab | b
sehingga aturan produksi yang telah disederhanakan dengan menghilangkan produksi unit adalah sebagai berikut :
S -> ab | b
S -> Aa
A -> ab | b
B -> ab
B -> b
C -> b
C -> ab
D -> b


Menghilangkan Produksi ε
Produksi ε adalah produksi dalam bentuk α -> ε atau bisa dianggap sebagai produksi kosong (empty).
penghilangan produksi  ε dilakukan dengan melakukan penggantian produksi yang memuat variable yang bisa menuju produksi ε, atau disebut Nullable.

Contoh :
terdapat tata bahasa bebas konteks sebagai berikut :
S -> aB | Cd
A -> d
C -> ε
Variable yang nullable adalah variable C, karena penurunan C -> ε merupakan penurunan satu2nya dari C. maka qita ganti S -> Cd menjadi S -> d. kemudian produksi C -> ε kita hapus.
Hasil penyederhanaannya adalah :
S -> aB | d
A -> d

Dalam prakteknya ketiga penyederhanaan tersebut dilakukan bersama pada suatu tata bahasa bebas konteks, yang nantinya menyiapkan tata bahasa bebas konteks tersebut untuk diubah kedalam suatu bentuk normal Chomsky (CNF).
Urutan dari penyederhanaan aturan produksi bebas konteks adalah sebagai berikut :

1. Hilangkan produksi ε
2. Hilangkan produksi unit
3. Hilangkan produksi useless

Smoga bermanfaat. jika ada yang kurang jelas dan sulit difahami, silahkan tinggalkan comment...;-)
Sumber : Dari berbagai sumber