Latihan Penyederhanaan Tata Bahasa Bebas Konteks

PENYEDERHANAAN TATA BAHASA BEBAS KONTEKS

Penyederhanaan tata bahasa bebas konteks bertujuan untuk melakukan pembatasan sehingga tidak menghasilkan pohon penurunan yang memiliki kerumitan atau aturan produksi yang tidak diperlukan. Perhatikan perumpamaan berikut : 

S → AB | a 

A → a 

Kelemahan tata bahasa bebas konteks di atas yaitu, aturan produksi S → AB tidak berarti karena B tidak memiliki penurunan.

LANGKAH – LANGKAH PENYEDERHANAAN

 
Beberapa cara untuk menyederhanakan tata bahasa bebas Konteks, terbagi menjadi 3:

1. Penghilangan produksi useless (tidak berguna)  

2. Penghilangan produksi unit. 

3. Penghilangan produksi є    

Penghilangan Produksi Useless
Penghilangan produksi useless, berikut syaratnya:

1. Menghilangkan produksi yang memuat simbol variabel yang tidak memiliki penurunan yang akan menghasilkan simbol terminal. 

2. Produksi yang tidak akan pernah dicapai dengan penurunan apapun dari simbol awal sehingga produksi itu redundan (berlebih).  

Penyederhanaan dengan penghilangan produksi Useless

S → aB | C

B → e |Ab

C → bCb | adF | ab

F → Cfb

Jawab:

B → Ab (A tidak memiliki penurunan)

F → cFB (F tidak memiliki penurunan keterminal)

C → adF (F tidak memiliki penurunan)

Hasil Akhir

S → aB | C

B → e

C → bCb | ab 

Penyederhanaan dengan penghilangan produksi Useless

S → Aa | B

A → ab | D

B → b | E

C → bb

E → aEa

Jawab :

A → D (D tidak memiliki penurunan)

C → bb (tidak memiliki penurunan)

E → aEa (tidak memiliki aturan produksi)

B → E (dihilangkan)

Hasil Akhir

S → Aa | B

A → ab

B → b

Penghilangan Produksi Unit  

Produksi unit adalah produksi di mana ruas kiri dan kanan aturan produksi hanya berupa satu Vn.

Perhatikan perumpamaan berikut : A → B, C → D.

 Keberadaan produksi unit membuat tata bahasa memiliki kerumitan yang tak perlu atau menambah  papanjang penurunan. Penyederhanaan ini dilakukan dengan melakukan penggantian aturan produksi unit.

Penyederhanaan dengan penghilangan produksi Unit

S → Aa | B

B → A | bb

A → a | bc | B

Jawab :

S → B

B → A

A → B

Hasil Akhir

S → Aa | a | bc | bb

B → a | bc | bb

A → bb

Penyederhanaan dengan penghilangan produksi Unit

S → A | Aa

A → B

B → C | b

C → D | ab

D → b

Jawab : 

S → A

A → B

B → C

C → D

Hasil Akhir

S → b | ab | b | Aa

A → b | ab | b

B → b | ab | b

C → b | ab

D → b

Penghilangan Produksi є

Produksi є adalah produksi dalam bentuk :  

α → є atau bisa dianggap sebagai produksi kosong (empty). 

Penghilangan produksi є dilakukan dengan melakukan penggantian produksi yang memuat variabel yang bisa menuju ke produksi є, atau biasa disebut nullable.

Penyederhanaan dengan penghilangan produksi Empty (ε)

S → AB

A → abB | aCa | ε

B → bA | BB | ε

C → ε

Jawab : 

Nullable A, B, C, S (dari S → AB)

S → AB | A | B

A → abB | ab

A → aa

B → bA | b

B → BB | B

C → ε, B → ε, A → ε (dihapus)

Hasil Akhir

S → AB | A | B

A → abB | ab | aa

B → bA | b | BB | B 

Penyederhanaan dengan penghilangan produksi Empty (ε)

S → aBCD | bb | A | ε

A → CDa | ef

B → b | Af | ε

C → BbC | ea

D → ε

Jawab : 

Nullable S, B, D

S → aBC | aC

A → Ca

C → BbC | bC

S → ε, B → ε, D → ε (dihapus)

Hasil Akhir

S → aBc | aC | bb | A

A → Ca | ef

B → b | Af

C → BbC | bC | ca

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

S → BACa

B → AC

A → dC | ε

C → D | ε

D → d

Jawab :

• C → ε (hapus)

S → BACa | BAa

B → AC | A

A → aC | ε | d

C → D

D → d

• A → ε

S → BACa | BAa | BCa | Ba

B → AC | A | C | ε

A → dC | d

C → D

D → d

• B → ε

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

B → AC | A | C

A → dC | d

C → D

D → d

Hasil Penghilang Unit

C → D

B → C

B → A

Menjadi,

C → d

C → d

C → dC | d

Hasil Akhir

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

B → AC | dC | d

A → dC | d

C → d

D → d

Hasil Penghilang Useless

Tidak terdapat syarat yang memenuhi.

Daftar Pustaka:

https://slideplayer.info/slide/12521759/ 

  

Selengkapnya:
Penyederhanaan dengan penghilangan produksi Useless
https://www.youtube.com/watch?v=83hpLytjYcQ 

Penyederhanaan dengan penghilangan produksi Unit
https://www.youtube.com/watch?v=gjoLtsLyDi0 

Penyederhanaan dengan penghilangan produksi Empty
https://www.youtube.com/watch?v=I5gfZvvR-ec&feature=youtu.be 

Penyederhanaan dengan penghilangan produksi Kompleks
https://www.youtube.com/watch?v=Uu-VwmP4Gxs