A. Penyederhanaan
Tata Bahasa Bebas Konteks
Tujuan
dari penyederhanaan adalah melakukan pembatasan sehingga tidak menghasilkan
pohon penurunan yang memiliki kerumitan yang tidak perlu atau aturan produksi
yang tidak berarti. Teknik penyederhanaan tata bahasa bebas konteks dibagi
menjadi 3 yaitu : Penghilangan Produksi Useless (tidak berguna), Penghilangan
Produksi Unit, dan Penghilangan produksi epsilon (ε).
1. Penghilangan
Produksi Useless
Produksi
useless didefinisikan sebagai:
a. Produksi
yang memuat simbol variabel yang tidak memiliki penurunan yang menghasilkan
terminal-terminal seluruhnya.
b. Produksi
yang tidak pernah dicapai dengan penurunan apapun dari simbol awal, sehingga produksi
itu redundan (berlebih).
Berikut
ini contoh penyederhanaan penghilangan produksi useless.
·
Soal
Latihan 1 :
Penyederhanaan
dengan penghilangan produksi Useless :
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.
Jawab :
Analisis
:
B → Ab (A tidak punya penurunan)
C → adF (F tidak memiliki aturan produksi yang menuju terminal)
F → cFB (F tidak memiliki aturan produksi yang menuju terminal dan tidak terjangkau dari start awal)
Hasil
penyederhanaan useless :
S → aB | C
B → e
C → bCb | ab
·
Soal
latihan 2 :
Penyederhanaan
dengan penghilangan produksi Useless :
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.
Jawab :
Analisis :
A → D (Simbol variabel D tidak memiliki penurunan).
B → E (E tidak memiliki aturan produksi yang menuju terminal).
C → bb (Aturan produksi C redundan/tidak terjangkau dari start awal).
E → aEa (Aturan produksi E redundan/tidak terjangkau dari start awal).
Hasil penyederhanaan useless
:
S → Aa | B
A → ab
B → b
2. Penghilangan
Produksi Unit
a. Produksi
dimana ruas kiri dan kanan aturan produksi hanya berupa satu simbol variable.
Misalkan : A → B, C → D.
b. Keberadaannya
membuat tata bahasa memiliki kerumitan yang tak perlu.
c. Penyederhanaan
dilakukan dengan melakukan penggantian aturan produksi unit.
Berikut ini contoh penyederhanaan
penghilangan produksi unit.
·
Soal
Latihan 1 :
Penyederhanaan
dengan penghilangan produksi Unit :
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.
Jawab :
Analisis
:
B → A (menjadi) B à a | bc
A → B (menjadi) A à bb
Hasil
penyederhanaan unit :
S → Aa | B
B → a | bc | bb
A → a | bc | bb
·
Contoh
Soal Latihan 2 :
Penyederhanaan
dengan penghilangan produksi Unit :
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.
Jawab :
Analisis
:
A → B (menjadi) A → b
B → C (menjadi) B → ab
C → D (menjadi) C → b
Hasil
penyederhanaan unit :
S → A | Aa
A → b | ab | b
B → b
| ab | b
C → b | ab
D → b
3. Penghilangan
Produksi Empty (ε)
Produksi ε adalah produksi dalam bentuk
α→ε, atau bisa dianggap sebagai produksi kosong. Penghilangan produksi ε
dilakukan dengan melakukan penggantian produksi yang memuat variabel yang bisa
menuju produksi ε, atau biasa disebut nullable.
Berikut
ini contoh penyederhanaan penghilangan produksi useless.
·
Soal
Latihan 1 :
Penyederhanaan
dengan penghilangan produksi Empty (ε) :
S → AB
A → abB | aCa | ε
B → bA| BB | ε
C → ε
Lakukan
penyederhanaan produksi empty / ε dengan :
1) Menghilangkan
produksi unit yang mengandung ε.
Jawab :
Analisis
:
o
C → ε (nullable dan
tidak memiliki produksi lain, maka produksi C dapat dihilangkan).
o
A → aCa, dapat
diganti menjadi A → aa, karena variable C nullable.
o
A nullable, tetapi A → ε bukan satu-satunya produksi dari A, maka A → abB | aCa
o
B nullable, tetapi B → ε bukan satu-satunya produksi dari B, maka B → bA| BB
Hasil
penyederhanaan empty (ε) :
S → AB | A | B
A → abB | ab | aCa |aa
B → bA | b | BB
·
Contoh
Soal Latihan 2 :
Penyederhanaan
dengan penghilangan produksi Empty (ε) :
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 ε.
Jawab :
Analisis
:
o
D → ε (nullable dan
tidak memiliki produksi lain, maka produksi C dapat dihilangkan).
o
B nullable, tetapi B → ε bukan satu-satunya produksi dari B, maka B → b | Af
o
S nullable, tetapi S → ε bukan satu-satunya produksi dari S, maka S→ aBCD | bb | A
Hasil
penyederhanaan empty (ε) :
S → aBCD | aBC | aCD | aC | bb | A
A → CDa | ef
B → b | Af
C → BbC | ea
B. Alur
Penyederhanaan Tata Bahasa Bebas Konteks
Urutannya
adalah sebagai berikut :
1) Hilangkan
produksi ε
2) Hilangkan
produksi unit
3) Hilangkan
produksi useless
·
Contoh
Soal Latihan Kompleks :
Lakukan penyederhanaan
pada himpunan produksi berikut dengan penghilangan empty+unit+useless
sekaligus.
S → BACa
B → AC
A → dC | ε
C → D | ε
D → d
Jawab :
Untuk melakukan
penyederhanaan pada soal diatas, menggunakan 3 langkah sebagai berikut.
1) Penghilangan
produksi empty (ε)
Analisis produksi empty :
o
A nullable, tetapi A → ε bukan satu-satunya produksi dari A, maka A → dC.
o
C nullable, tetapi C → ε bukan satu-satunya produksi dari C, maka C → D.
Hasil penyederhanaan empty (ε) :
S → BACa | BCa | BAa | Ba
B → AC | A | C
A → dC | d
C → D
D → d
2) Penghilangan
produksi unit
Analisis produksi unit :
C → D (menjadi) C → d
B → AC | A | C (menjadi) B → dd | d
A → dC | d (menjadi) A → dd | d
Hasil penyederhanaan unit :
S → BACa | BCa | BAa
| Ba
B → dd | d
A → dd | d
C → d
D → d
3) Penghilangan
produksi useless :
Analisis produksi useless :
D → d (Aturan
produksi D redundan/tidak terjangkau dari start awal, sehingga dapat dihilangkan).
Hasil penyederhanaan useless :
S → BACa | BCa | BAa
| Ba
B → dd | d
A → dd | d
C → d
C. Video
Penyederhanaan Tata Bahasa Bebas Konteks
Dibawah
ini kalian dapat menonton pembahasan lengkap mengenai penjelasan materi diatas.
DAFTAR PUSTAKA
Tidak ada komentar:
Posting Komentar