PENYEDERHANAAN TATA BAHASA BEBAS KONTEKS

Melakukan pembatasan sehingga tidak menghasilkan pohonp enurunan yang memiliki kerumitan yang tak perlu atau aturan produksi yang tidak berarti.

Contoh:

S → AB | a

A → a

Kelemahannya:  aturan produksiAB menjadi tidak berarti karena B tidak memiliki penurunan.

Suatu tata bahasa bebas konteks dapat disederhanakan dengan melakukan cara berikut ini :

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

Penghilangan Produksi Useless

Produksi useless adalah :

• Produksi yang memuat simbol variabel yang tidak memiliki penurunan yang akan menghasilkan terminal-terminal seluruhnya (masih ada simbol variabel yang tersisa)
• Produksi yang tidak akan pernah dicapai dengan penurunan apapun dari simbol awal sehingga produksi itu redundan(berlebih).

Contoh:

S → aSa | Abd | Bde

A → Ada

B → BBB | a

C → h

Dapat disimpulkan:

1. Simbol variable A tidak memiliki penurunan yang menuju terminal jadi bisa dihilangkan.
2. Konsekuensi dari  no (1), aturan S →  Abd tidak memiliki penurunan
3. C → h adalah Redundan

Maka tata bahasa bebas konteks setelah disederhanakan menjadi :

S → aSa | Bde

B → BBB | a

Penghilangan Produksi Unit

Produksi unit adalah produksi dimana ruas kiri dan kanan aturan produksi hanya berupa satu symbol variabel, misalkan :

A → B

C → D

Contoh:

S → Sb

S → C

C → D

C → ef

D → dd

Kita lakukan penggantian (PenghilanganProduksi Unit) berurutan mulai dari aturan produksi paling dekat menuju terminal-terminal

C  → D →  C  → dd

S  → C   → S  → dd| ef

Aturan Produksi setelah penyederhanaan :

S  → Sb

S → dd| ef

C  → dd

C  → ef

D  → dd

Penghilangan Produksi ε  

Produksi ε adalah produksi dalam bentuk

 a → ε

 atau bisa dianggap sebagai produksi kosong.

Penghilangan produksi ε dilakukan dengan penggantian produksi yang memuat variabel yang bisa menuju produksiε atau biasa disebut nullable.

Contoh :

S →bcAd

A → ε

Pada kasus diatas A nullable, maka variabel A bisa ditiadakan.

Hasil penyederhanaan

S →bcd

Contoh Soal :

Penyederhanaan dengan penghilangan produksi Useless

Latihan 1

S → aB| C

B→ e |Ab

C→ bCb| adF| ab

F → cFB

Lakukan penyederhanaan produksi useless dengan:

1. Menganalisis  Vn  yang  tidak  memiliki  turunan  atau  Vn  yang  tidak pernah berhenti pada Vt, kemudian hilangkanlah.
2. Redudant/ Berlebih/ tidak terjangkau dari start awal.

Pembahasan :

S → aB| C

B→ e |Ab   

(Simbol variabel A tidak memiliki penurunan yang menuju terminal, sehingga bisa dihilangkan)

C→ bCb| adF| ab       

 (Simbol variabel F tidak memiliki penurunan yang menuju terminal, sehingga bisa dihilangkan)

F → cFB                     

(Simbol variabel F tidak memiliki penurunan yang menuju terminal, sehingga bisa dihilangkan)

Hasil penyederhanaan menjadi

S → aB| C

B→ e

C→ bCb| ab  

Latihan 2

S → Aa| B

A → ab| D

B → b | E

C → bb

E → aEa

Lakukan penyederhanaan produksi useless dengan:

1. Menganalisis  Vn  yang  tidak  memiliki  turunan  atau  Vn  yang  tidak pernah berhenti pada Vt, kemudian hilangkanlah.
2. Redudant/ Berlebih/ tidak terjangkau dari start awal.

Pembahasan :

S → Aa| B

A → ab| D       

(Simbol variabel D tidak memiliki penurunan yang menuju terminal, sehingga bisa dihilangkan)

B → b | E

C → bb           

(Simbol variabel C tidak memiliki penurunan untuk C itu sendiri, sehingga bias dihilangkan)

E → aEa         

(Simbol variabel E tidak memiliki penurunan untuk E itu sendiri, sehingga bias dihilangkan)

Hasil penyederhanaan menjadi

S → Aa| B

A → ab

B → b

Penyederhanaan dengan penghilangan produksi Unit

Latihan 1

S → Aa| B

B → A | bb

A → a | bc| B

Lakukan penyederhanaan produksi unit dengan:

1. Penghilangan pada produksi unit yang ruas kiri dan kanannya satu symbol variable non terminal, dan tidak memiliki turunan.

Pembahasan :

Dilakukan penggantian berturutan mulai dari aturan produksi yang paling dekat menuju ke penurunan terminal-terminal (‘=>’ dibaca ‘menjadi’)

A → B => A → a | bc | bb

B → A => B → a | bc | bb

Hasil penyederhanaan menjadi

S → Aa| a | bc | bb

B → a | bc | bb

A → a | bc | bb

Latihan 2

S  → A | Aa

A → B

B → C | b

C → D | ab

D → b

Lakukan penyederhanaan produksi unit dengan:

1. Penghilangan pada produksi unit yang ruas kiri dan kanannya satu symbol variable non terminal, dan tidak memiliki turunan.

Pembahasan :

Dilakukan penggantian berturutan mulai dari aturan produksi yang paling dekat menuju ke penurunan terminal-terminal (‘=>’ dibaca ‘menjadi’)

C → D  => C →  b | ab

B → C  => B →  b | ab | b

A → B  => A →  b | ab | b

S → A  => b | ab | b | Aa

Hasil penyederhanaan menjadi

S →  b | ab | b | Aa

A →  b | ab | b

B →  b | ab | b

C →  b | ab

D → b

Penyederhanaan dengan penghilangan produksi Empty (ε)

Latihan 1

S → AB

A → abB| aCa | ε

B → bA| BB | ε

C → ε

Lakukan penyederhanaan produksi Empty/ε dengan:

1. Menghilangkan produksi unit yang mengandung ε

Pembahasan :

Step 1 (Menghilangkan nullable C)

S → AB

A → abB| aCa | ε

B → bA| BB | ε

C → ε

Menjadi 

S → AB

A → abB| aa | ε

B → bA| BB | ε

Step 2 (Menghilangkan nullable B)

S → AB

A → abB| aCa | ε

B → bA| BB | ε 

Menjadi

S → AB →A

A → ab| aa | ε

B → bA

Step 3 (Menghilangkan nullable A)

S → AB

A → abB| aCa | ε

B → bA

 Menjadi

S → AB → A → B

A → ab| aa  

B → b

Hasil penyederhanaan menjadi

S → AB → A → B

A → ab| aa  

B → b

Latihan 2

S  → aBCD | bb | A | ε

A  → CDa | ef

B  → b | Af | ε

C  → BbC | ea

D  → ε

Lakukan penyederhanaan produksi Empty/ε dengan:

1. Menghilangkan produksi unit yang mengandung ε

Pembahasan :

Step 1 (Menghilangkan nullable D)

S  → aBCD | bb | A | ε

A  → CDa | ef

B  → b | Af | ε

C  → BbC | ea

D  → ε

Menjadi

S  → aBC | bb | A | ε

A  → Ca | ef

B  → b | Af | ε

C  → BbC | ea

Step 2 (Menghilangkan nullable B)

S  → aBC | bb | A | ε

A  → Ca | ef

B  → b | Af | ε

C  → BbC | ea 

Menjadi

S  → aC | bb | A | ε

A  → Ca | ef

B  → b | Af |

C  → bC | ea

Hasil penyederhanaan menjadi

S  → aC | bb | A | ε

A  → Ca | ef

B  → b | Af |

C  → bC | ea

Latihan Kompleks

Lakukan penyederhanaan pada himpunan produksi berikut dengan penghilangan empty + unit + useless sekaligus.

S  →  BACa

B  →  AC

A  →  dC | ε

C  →  D | ε

D  →  d

Pembahasan :

Produksi Empty

Step 1 (Menghilangkan nullable )

S  →  BACa

B  →  AC

A  →  dC | ε

C →  D | ε

D  →  d

Hasil Penyederhanaannya

S  →  BACa | BAa | BCa | Ba

B  →  AC | A | C

A  →  dC | d

C  →  D

D  →  d

Produksi Unit

Hasil Penyederhanaannya

S  →  BACa | BAa | BCa | Ba

B  →  AC | dC | d

A  →  dC | d

C  →  D

D  →  d

Produksi Useless

Hasil Penyederhanaannya

S  →  BACa | BAa | BCa | Ba

B  →  AC | dC | d

A  →  dC | d

C dan D tidak termasuk karena keduanya redudan

Untuk lebih jelasnya bisa menyaksikan video dibawah ini

Daftar Pustaka :
http://herilovemetallica.blogspot.com/2009/10/penyederhanaan-tata-bahasa-dalam-teori.html
https://kikifaradilla.wordpress.com/2015/03/20/tata-bahasa-bebas-konteks-teori-bahasa-automata/