PENYEDERHANAAN TATA BAHASA BEBAS KONTEKS

TUJUAN PENYEDERHANAAN

Melakukan pembatasan sehingga tidak menghasilkan pohon penurunan yang memiliki kerumitan yang tak perlu atau aturan produksi yang tidak berarti.
contoh :
S → AB | a
A → a
Kelemahannya : aturan produksi AB 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 1 :
S → aSa | Abd | Bde
A → Ada
B → BBB | a
C → h
Dapat disimpulkan :
1. Simbol variabel 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

CONTOH 2 :
S → aB I C
A → bcD I dAC
B → e I Ab
C → bCb I adF I ab
F → cFB

Useless :
1. A → bcD (D tidak punya penurunan)
2. A → dAC (A tidak punya penurunan ke terminal)
3. B → Ab ( A tidak punya penurunan)
4. F → cFB (F tidak punya penurunan ke terminal)

5. C → adF (F tidak punya penuruanan)

Hasil Penyederhanaan Useless :
S → aB I C
B → e

C → bCb I ab

PENGHILANGAN PRODUKSI UNIT

Produksi unit adalah produksi dimana ruas kiri dan kanan aturan produksi hanya berupa satu simbol variabel,

misalkan A → B, C → D

CONTOH 1 :

S → Sb

S → C

C → D

C → ef

D → dd

Kita lakukan penggantian (Penghilangan Produksi 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 EMPTY (ε)

Produksi E 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 → bcAd

A → ε

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

Hasil penyederhanaan

S → bcd

CONTOH 2 :

S → bcAd

A → bd | εε

Hasil penyederhanaan

S → bcAd | bcd

A → bd

ALUR PENYEDERHANAAN TATA BAHASA BEBAS KONTEKS

CFG --> PENGHILANGAN PRODUKSI ε --> PENGHILANGAN PRODUKSI UNIT --> PENGHILANGAN PRODUKSI USELESS --> CFG YANG SUDAH DISEDERHANAKAN

CONTOH 1 :

S → dA I Bd

A → bc

A → ε

B → c

Kondisi :

A nullable tapi A → ε bukan penurunan satu2nya dari A

Maka :

S → dA I d I Bd

A → bc

B → c

S → AaCD

A → CD | AB

B → b | ε

C → d | ε

D → ε

Jawab :

Var yang nullable : B, C, D.

D → ε, maka

S → AaCD => S → AaC

A → CD => A → C

D → ε dihapus.

B → ε, maka

A → AB => A → AB|A

B → ε dihapus

C → ε, maka

S → AaC =>S → AaC|aA

C → ε dihapus

Setelah Penyederhanaan :

S → Aac|Aa

A → C|AB|A

B → b

C → d

SOAL LATIHAN

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.

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.

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 simbol variable non terminal, dan tidak memiliki turunan.

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 simbol variable non terminal, dan tidak memiliki turunan.

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 ε

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 ε.

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

S → BACa
B → AC
A → dC | ε
C → D | ε

D → d

Untuk jawaban dari soal latihan diatas adalah seperti dibawah ini berikut dengan video penjelasannya .

Jawaban Penyederhanaan dengan penghilangan produksi Useless