PENYEDERHANAAN TATA BAHASA BEBAS KONTEKS

Dalam materi tata bahasa automata terdapat materi mengenai penyederhanaan. Penyederhanaan ini mengenai bagaimana suatu gramar atau ekspresi reguler di tata bahasa bebas konteks yang rumit tapi bisa disederhanakan. Oleh itu, tujuan dari penyederhaantata bahasa bebas konteks ialah untuk melakukan pembatasan pada bahasa agar nantinya tidak menciptakan keturunan yang rumit, tak perlu dilakukan dan atau mengurangi produksi yang tak berarti.

Dalam penyederhaan ini memiliki tiga tipe atau jenis penyederhanaan yaitu :

1. Penghilangan produksi Useless 
2. Penghilangan produksi Unit
3. Penghilangan produksi Empty (ε)
4. Kompleks (gabungan dari ketiganya)

Berikut penjelasan dan cara penyederhaan dari tiga tipe penyederhaan diatas.

1. Penghilangan Produksi Useless

Adalah produksi yang memuat symbol variabel yang tidak manghasilkan keturuanan kepada terminal terminal. Sehingga ini akan mengurangi produksi yang tidak diperlukan. Pada penghilangan produksi useless juga kita bisa mengurangi atau mengapus bahasa yang bersifat redundan (sebuah produksi yang tidak akan dicapai dari awal produksi dimulai).

• Contoh 1 :

S --> aB | C

B --> e | Ab

C --> bCb | adF | ab

F --> cFB

Untuk mempermudah penyederahaan kita dapat menguraikan terlebih dahulu satu per satu produksi yang memiliki lebih satu terminal, setelah itu kita mengidentifikasi mana yang tidak menghasilkan terminal, tidak memimiliki penurunan dan redundan. Seperti ini :

S --> aB 

S --> C

B --> e

B --> Ab (A tidak memiliki penurunan karena tidak produksi variabel A)

C --> bCb

C --> adF (F tidak memiliki penurunan, akibat F --> cFB yang akan dihilangkan)

C --> ab

F --> cFB (F tidak mempunyai penurunan ke terminal lainnya, ini berdampak pada produksi C --> adF)

Sehingga hasilnya menjadi :

S --> aB | C

B --> e 

C --> bCb | ab

• Contoh 2 :

S --> Aa| B

A --> ab| D

B --> b | E

C --> bb

E --> aEa

Untuk mempermudah penyederahaan kita dapat menguraikan terlebih dahulu satu per satu produksi yang memiliki lebih satu terminal, setelah itu kita mengidentifikasi mana yang tidak menghasilkan terminal, tidak memimiliki penurunan dan redundan. Seperti ini :

S --> Aa

S --> B

A --> ab

A --> D (D tidak memiliki penurunan karena tidak produksi variabel D)

B --> b

B --> E (E tidak memiliki penurunan, akibat E --> aEa yang akan dihilangkan) 

C --> bb (redudan, karena tidak ada produksi yang memanggil varibel C)

E --> aEa (E tidak mempunyai penurunan ke terminal lainnya, ini berdampak pada produksi B --> E)

Sehingga hasilnya menjadi :

S --> Aa| B

A --> ab

B --> b

2. Penghilangan Produksi Unit

Adalah produksi dimana ruas kiri dan kanannya hanya memiliki satu varibel seperti S --> A, A --> B, B --> C. Dengan aturan atau cara ini kita bisa mendapatkan produksi yang sederhana. Pada produksi unit kita akan mengubah varibel seperti diatas menjadi terminal.

• Contoh 1 :

S --> Aa| B

B --> A | bb

A --> a | bc| B

Kita akan mengubah produksi yang memiliki aturan seperti S --> A, A --> B, B --> C dan itu berlaku pada produksi :

S --> B

B --> A

A --> B

Lalu, bagaimana mengubahnya menjadi terminal ? kita lihat lagi pada soalnya. Ambilah variabel yang dekat terlebih dahulu pada terminal seperti :

pertama,

A --> B (karena terdapat produksi B --> bb)

maka, A --> bb

kedua,

B --> A (karena kita bisa mengubahya setelah A --> B telah berubah) 

maka, B --> a | bc | bb (pada soal B --> A | bb , kita tidak perlu menambah bb menjadi dua karena sama saja).

terakhir,

S --> B (dari sebelumnya B telah mendapatkan perubahan)

maka S --> a | bc | bb 

Sehingga hasilnya menjadi :

S --> Aa | a | bc | bb

B --> a | bc | bb

A --> a | bc | bb

• Contoh 2 :

S --> A | Aa

A --> B

B --> C | b

C --> D | ab

D --> b

Kita akan mengubah produksi yang memiliki aturan seperti S --> A, A --> B, B --> C dan itu berlaku pada produksi :

S --> A

A --> B

B --> C

C --> D

Lalu, bagaimana mengubahnya menjadi terminal ? kita lihat lagi pada soalnya. Ambilah variabel yang dekat terlebih dahulu pada terminal seperti :

pertama,

C --> D (karena D memiliki terminal terdekat)

maka, C --> b

kedua,

B --> C (karena C telah diubah)

maka, B --> b | ab (jika kamu bingung ab didpat darimana maka kamu bisa cek kembali soalnya)

ketiga,

A --> B

maka, A --> b | ab (meski sama itu tidak apa apa)

terakhir,

S --> A

maka, S --> b | ab

Sehingga hasilnya menjadi :

S --> ab | b | Aa

A --> ab | b

B --> ab | b

C --> b | ab

D --> b

3. Penghilangan Produksi Empty atau null (𝜺)

Adalah produksi dalam bentuk 𝜶 --> 𝜺 atau bisa dianggap sebagai produksi kosong. Penghilangan produksi 𝜺 dilakukan dengan penggantian produksi yang memuat variabel yang bisa menuju produksi 𝜺 atau biasa disebut nullable.

• Contoh 1 :

S --> AB

A --> abB | aCa | ε

B --> bA | BB | ε

C --> ε

Dari soal kita bisa mengetahui dengan jelas variabel atau produksi yang memiliki nilai null atau nullable yaitu A, B dan C. Setelah mengetahui produksi mana yang memiliki nilai null  maka kita bisa menghapusnya.

maka hasil nya menjadi :

• S --> AB | A | B (ini karena pada A terdapat null dan B juga terdapat null maka akan ada suatu kondisi dimana produksi pada S tidak memiliki A dan atau B) 
• A --> abB | ab | aa (ini karena pada B terdapat null maka akan ada suatu kondisi dimana produksi pada A tidak memiliki B)
• B --> bA | b | BB | B (ini karena pada A terdapat null dan B juga terdapat null maka akan ada suatu kondisi dimana produksi pada B tidak memiliki A dan atau B)
• Produksi C tidak dituliskan karena hanya memiliki ε (tidak ada terminal lain)

S --> AB | A | B

A --> abB | ab | aa

B --> bA | b | BB | B

• Contoh 2 :

S --> aBCD| bb | A | ε

A --> CDa| ef

B --> b | Af| ε

C --> BbC| ea

D --> ε

Dari soal kita bisa mengetahui dengan jelas variabel atau produksi yang memiliki nilai null atau nullable yaitu S, B dan D. Setelah mengetahui produksi mana yang memiliki nilai null  maka kita bisa menghapusnya.

maka hasilnya menjadi :

• S --> aBC| aC | bb | A (ini karena pada B terdapat null dan D juga terdapat null maka akan ada suatu kondisi dimana produksi pada S tidak memiliki B dan atau D)
• A --> Ca| ef
• B --> b | Af
• C --> BbC | bC | ea  (ini karena pada B terdapat null maka akan ada suatu kondisi dimana produksi pada C tidak memiliki B)
• Produksi D tidak dituliskan karena hanya memiliki ε (tidak ada terminal lain)

S --> aBC| aC | bb | A

A --> Ca| ef
B --> b | Af

C --> BbC | bC | ea

4. Kompleks

Adalah penyederhanaan yang dilakukan dengan menggunakan ketiga cara penyederhanaan diatas. Dalam melakukan penyederhanaannya kita mengikuti alur penyederhaan tata bahasa bebas konteks.

Jika kamu mendapatkan produksi yang harus disederhanakan secara kompleks maka kamu ingatlah alur ini.

• Contoh :

S --> BACa

B --> AC

A --> dC| ε

C --> D | ε

D --> d

Berikut tahapan pengerjaanya :

Pertama gunakan penghilangan produksi empty atau null

maka, nullable nya A dan C

S --> BACa

B --> AC | A | C

A --> dC | d

C --> D

D --> d

Kedua gunakan penghilangan produksi unit

maka, 

C --> D             C --> d

B --> A              B --> dC | d

B --> C              B --> d

hasil sementara :

S --> BACa | BAa | BCa

B --> AC | dc | d

A --> dC | d

C --> d

D --> d

Terakhir, gunakan penghilangan produksi useless

dapat terlihat produksi D tidak dijangkau di produksi lain maka D adalah redundan

hasil akhirnya menjadi :

S --> BACa | BAa | BCa

B --> AC | dc | d

A --> dC | d

C --> d

Berikut video penuturan dari saya

Link video :

Gdrive

_______________________________________________________________________________________________________________________

Daftar Pustaka

1. Materi Persentasi "Penyederhaan Tata Bahasa Bebas Konteks" Dosen pengampu Teori Bahasa Automata Bapak Garno, M.Kom. Fakultas Ilmu Komputer Universitas Singaperbangsa Karawang.
2. online : https://herilovemetallica.blogspot.com/2009/10/penyederhanaan-tata-bahasa-dalam-teori.html
3. online : https://slideplayer.info/slide/3649861/