Gadget Bovung

PENYEDERHANAAN TATA BAHASA BEBAS KONTEKS

Penyederhanaan tata bahasa bebas konteks adalah melakukan pembatasan sehingga tidak menghasilkan pohon penurunan yang memiliki kerumitan yang tak perlu atau aturan produksi yang tidak berarti.

Suatu tata bahasa bebas konteks dapat disederhanakan dengan melakukan :

Produksi useless didefinisikan sebagai :

Produksi yang memuat simbol variabel yang tidak memiliki penurunan yang akan menghasilkan terminal-terminal seluruhnya, produksi ini tidak berguna karena bila diturunkan tidak akan pernah selesai.

Produksi yang tidak akan pernah di capai dengan penurunan apapun dari simbol awal, sehingga produksi itu redundan (berlebih)

Contoh menghilangkan produksi useless :

              S → aB | C

  B → e |Ab

                          C → bCb | adF | ab

                          F → cFB

Analisis :

B → | Ab ( A tidak punya penurunan , sehingga harus dihilangkan)

F → cFB ( F tidak ada turunan keterminal , sehingga harus dihilangkan)

                             C → adF ( Karena F sudah di hilangkan , maka  C → adF harus dihilangkan karena useless)

B.Penghilangan produksi unit

Produksi unit adalah produksi dimana ruas kiri dan kanan aturan produksinya hanya berupa satu simbol variabel misalnya :

A → B, C → D

Keberadaannya membuat tata bahasa memiliki kerumitan yang tak perlu. Penyederhanaan dilakukan dengan melakukan penggantian aturan produksi unit. Kita lakukan penggantian (Penghilangan Produksi Unit) berurutan mulai dari aturan produksi paling dekat menuju terminal- terminal.

Contoh penghilangan produksi unit :

S → Aa | B

B → A | bb

A → a | bc | B

Analisis :

Kalau dilihat dari dari teori yang marker merah maka A → B bisa diganti menjadi A → bb.

Sehingga :

A → a | bc | bb

Lalu B → A | bb  bisa diubah menjadi

B → a | bc | bb

Lalu S → Aa | B pun bisa diubah menjadi

S → Aa | a | bc | bb

Sehingga hasilnya menjadi :

S → Aa | a | bc | bb

B → a | bc | bb

               A → a | bc | bb

C. PenghilangProduksi  ε

Produksi ε adalah produksi dalam bentuk :

a → ε

atau bisa dianggap sebagai produksi kosong ( empty ). Penghilangan produksi ε dilakukan dengan melakukan penggantian produksi yang memuat variabel yang bisa menuju produksi ε, atau biasa disebut nullable.

Prinsip penggantiannya bisa dilihat kasus berikut:

S → bcAd

A → ε

A nullable serta A → ε satu-satunya produksi dari A, maka variabel A bisa ditiadakan, hasil penyederhanaan tata bahasa bebas konteks menjadi:

S → bcd

Tetapi bila kasusnya:

S → bcAd

A → bd | ε

A nullable, tapi A → ε bukan satu-satunya produksi dari A, maka hasil penyederhanaan:

S → bcAd | bcd

A → bd

Contoh penghilang produksi  ε :

S → AB

A → abB | aCa | ε

B → bA | BB | ε

C → ε

Langkah pertama hilangkan  C, setelah dihilangkan maka akan menjadi :

S → AB

A → abB | aa | ε

B → bA | BB | ε

Langkah kedua hilangkan B yang mengandung ε, sehingga menjadi :

S → AB | A

A → abB | aa | ε | ab

B → bA | BB

Langkah ketiga hilangkan A yang mengandung ε, setelah dihilangkan menjadi,

S → AB | A | B

A → abB | aa | ab

B → bA | BB | b

Ketika sudah tidak ada ε maka sudah selesai.

Kesimpulan

Dari semua teknik , untuk menyelesaikan suatu penyederhanaan yang kompleks, terdapat alur yang harus dijalani.

Alur penyederhanaan Tata Bahasa :

Contoh Soal Kompleks :

S → BACa

B → AC

A → dC | ε

C → D | ε

D → d

Langkah pertama adalah hilangkan semua ε,  langkah 1 hilangkan C → ε, makan akan menjadi :

S → BACa | BAa

B → AC | A

A → dC | ε | d

C → D

D → d

selanjutnya hilangkan A → ε, makan akan menjadi :

S → BACa | BAa | BCa | Ba

B → AC | A | C | ε

A → dC | d

C → D

D → d

selanjutnya hilangkan  B → ε,maka akan menjadi :

S → BACa | BAa | BCa | Ba | ACa | Aa | Ca | a

B → AC | A | C

A → dC | d

C → D

D → d

Langkah kedua menghilangkan produksi unit

C → D (diubah menjadi C → d )

B → C (diubah menjadi B → d )

B → A (diubah menjadi B → dC | d )

Sehingga menjadi,

S → BACa | BAa | BCa | Ba | ACa | Aa | Ca | a

B → AC | dC | d

A → dC | d

C → d

D → d

Langkah ketiga adalah penghilangan produksi useless, dalam kasus ini , D → d adalah useless (Redundant) sehingga harus dihapus.

Jadi hasil akhirnya adalah :

S → BACa | BAa | BCa | Ba | ACa | Aa | Ca | aB → AC | dC | d

A → dC | d

C → d