Materi 5 Penyederhanaan Tata Bahasa Bebas Konteks

Tujuan : 
• Melakukan pembatasan sehingga tidak menghasilkan pohon penurunan yang memiliki kerumitan yang tak perlu atau aturan produksi yang tidak berarti

Contoh :
S → AB | a
S → a

Cara Penyederhanaan:
1. Penghilangan produksi useless ( tidak berguna )
2. Penghilangan produksi unit
3. Penghilangan produksi e

Penghilangan Produksi Useless
Di sini produksi useless didefinisikan sebagai :
- Produksi yang memuat symbol variabel yang tidak memiliki penurunan yang akan menghasilkan terminal-terminal seluruhnya.
- 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

Maka
1) Simbol variabel A tidak memiliki penurunan yang menuju terminal, sehingga bisa
dihilangkan
2) Konsekuensi no (1), aturan produksi S → Abd tidak memiliki penurunan

Penyederhanaan menjadi:
S → aSa | Bde
B → BBB | a

Contoh :
S → Aa | B
A → ab | D
B → b | E
C → bb
E → aEa

Maka :
1) Aturan produksi A → D, simbol variabel D tidak memiliki penurunan.
2) Aturan produksi C → bb, Penurunan dari simbol S, dengan jalan manapun tidak
akan pernah mencapai C
3) Simbol variabel E tidak memiliki aturan produksi yang menuju terminal
4) Konsekuensi no (3) Aturan produksi B → E, simbol variabel E tidak memiliki
penurunan.
maka produksi yang useless:
A → D
C → bb
E → aEa
B → E
Penyederhanaannya menjadi:
S → Aa | B
A → ab
B → b

Penghilangan Produksi Unit
Produksi dimana ruas kiri dan kanan aturan produksi hanya berupa satu simbol variabel,
misalkan: A → B, C → D.
Keberadaannya membuat tata bahasa memiliki kerumitan yang tak perlu.
Penyederhanaan dilakukan dengan melakukan penggantian aturan produksi unit.

Contoh:
S → Sb
S → C
C → D
C → ef
D → dd

Dilakukan penggantian berturutan mulai dari aturan produksi yang paling dekat menuju
ke penurunan terminal-terminal (‘=>’ dibaca ‘menjadi’):
C → D => C → dd S → C => S → dd | ef

Sehingga aturan produksi setelah penyederhanaan:
S → Sb
S → dd | ef
C → dd
C → ef
C → dd

Penghilangan Produksi ε
Produksi ε adalah produksi dalam bentuk :
a → ε

atau bisa dianggap sebagai produksi kosong ( empty ). Penghilangan produksi e
dilakukan dengan melakukan penggantian produksi yang memuat variabel yang bisa
menuju produksi e, 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 → e bukan satu-satunya produksi dari A, maka hasil
penyederhanaan:

S → bcAd | bcd
A → bd


Contoh :
S → Ab | Cd
A → d
C → ε

Variabel yang nullable adalah variabel C. Karena penurunan C → ε merupakan
penurunan satu-satunya dari C, maka kita ganti S → Cd menjadi S → d. Kemudian
produksi C → ε kita hapus.

Setelah penyederhanaan menjadi:

S → Ab | d
A → d