Penyederhanaan ini bertujuan untuk melakukan
pembatasan agar tidak menghasilkan pohon penurunan yang memiliki kerumitan yang
tidak perlu atau aturan produksi yang tidak berarti.
Penyederhanaan
dapat dilakukan dengan teknik berikut :
A.
Penghilangan
produksi useless.
B.
Penghilangan
produksi unit.
C.
Penghilangan
produksi e
(empty).
a.
Penghilangan Produksi Useless
Produksi yang memuat simbol variable yang tidak
memiliki penurunan yang akan menghasilkan terminal-terminal seluruhnya (menuju
terminal), produksi ini tidak berguna karena bila diturunkan tidak akan pernah
selesai (masih ada simbol variable tersisa). Produksi yang tidak akan pernah
dicapai dengan penurunan apapun dari simbol awal, sehingga produksi itu
redundan (berlebih).
Langkah Penyederhanaannya :
1.
Hilangkan aturan
yang tidak menuju terminal.
2.
Hapus anggota S
yang mengandung simbol ke terminal yang tidak berguna.
3.
Hilangkan
redundan (anggota yang tidak ada di S dan sebaliknya).
Contoh :
1.
S → aB | C
B → e |Ab
C → bCb | adF | ab
F → cFB
Jawab :
§ Langkah Pertama
Hilangkan F → cFB
karena tidak menuju ke terminal.
Sehingga menjadi :
S → aB | C
B → e |Ab
C → bCb | ab (adF
dihilangkan karena F sudah tidak memiliki penurunan).
§ Langkah Kedua
Hilangkan B → Ab karena
A tidak memiliki penurunan.
Sehingga menjadi :
S → aB | C
B → e
C → bCb | adF | ab
F → cFB
§ Maka hasil akhir penyederhanaan produksi useless dari
soal diatas adalah :
S → aB | C
B → e
C → bCb | adF | ab
F → cFB
2.
S → Aa | B
A → ab | D
B → b | E
C → bb
E → aEa
Jawab :
§ Langkah Pertama
Hilangkan E → aEa
karena E tidak menuju ke terminal.
Sehingga menjadi :
S → Aa | B
A → ab | D
B → b (E dihilangkan
karena E sudah tidak memiliki penurunan)
C → bb
§ Langkah Kedua
Hilangkan C → bb karena
C redundan.
Sehingga menjadi :
S → Aa | B
A → ab | D
B → b
§ Langkah Ketiga
Hilangkan A → D Karena
D tidak memiliki penurunan.
S → Aa | B
A → ab
B → b
§ Maka hasil akhir penyederhanaan produksi useless
dari soal diatas adalah :
S → Aa | B
A → ab
B → b
b.
Penghilangan Produksi Unit
Produksi unit adalah produksi yang ruas kiri dan
kanan aturan produksinya hanya berupa satu simbol variable misalkan: A → B. ( a = 1 N/V dan b = 1 N/V )
Dengan adanya bentuk produksi unit ini membuat tata bahasa memiliki kerumitan
yang tidak perlu atau menambah panjang penurunan. Penyederhanaan ini dilakukan
dengan melakukan penggantian aturan produksi unit.
Langkah Penyederhanaannya :
1.
Jabarkan
masing-masing himpunan.
2.
Sederhanakan
ruas kiri dan ruas kanan yang hanya berupa variabel simbol sama.
3.
Hapus simbol
variabel yang tidak berguna / tidak mempunyai turunan.
Contoh :
1.
S → Aa | B
B → A | bb
A → a | bc | B
Jawab :
§ Langkah Pertama
Ubah A → B menjadi A → A
| bb (namun A tidak usah di masukan karena akan useless).
Sehingga menjadi :
S → Aa | B
B → A | bb
A → a | bc | bb
§ Langkah Kedua
Ubah B → A menjadi B →
a | bc
Sehingga menjadi :
S → Aa | B
B → a | bc | bb
A → a | bc | bb
§ Langkah Ketiga
Ubah S → B menjadi S → a
| bc | bb
Sehingga menjadi :
S → Aa | a | bc | bb
B → a | bc | bb
A → a | bc | bb
§ Maka hasil akhir penyederhanaan unit dari soal diatas
adalah :
S → Aa | a | bc | bb
B → a | bc | bb
A → a | bc | bb
2.
S → A | Aa
A → B
B → C | b
C → D | ab
D → b
Jawab :
§ Langkah Pertama
Ubah C → D menjadi C →
b
Sehingga menjadi :
S → A | Aa
A → B
B → C | b
C → b | ab
D → b
§ Langkah Kedua
Ubah B → C menjadi B →
b | ab
Sehingga menjadi :
S → A | Aa
A → B
B → b | ab (bukan B → b
| ab | b karena b sudah ada, jadi hanya ditulis satu kali)
C → b | ab
D → b
§ Langkah Ketiga
Ubah A → B menjadi A →
b | ab
Sehingga menjadi :
S → A | Aa
A → b | ab
B → b | ab
C → b | ab
D → b
§ Langkah Keempat
Ubah S → A menjadi S →
b | ab
S → b | ab | Aa
A → b | ab
B → b | ab
C → b | ab
D → b
§ Maka hasil akhir penyederhanaan unit dari soal diatas
adalah :
S → b | ab | Aa
A → b | ab
B → b | ab
C → b | ab
D → b
c.
Penghilangan produksi e (empty)
Produksi e (Empty) adalah produksi dalam bentuk a → e atau bisa
dianggap sebagai produksi kosong. Penghilangan produksi e dilakukan dengan melakukan penggantian produksi
yang memuat variable yang menuju ke produksi e, atau biasa disebut nullable.
Langkah Penyederhanaannya :
1. Hilangkan simbol
yang terdapat e
(empty) dalam himpunan produksi.
2. Simbol variabel
tidak di hapus jika terdapat cabang teriminal/variabel yang saling berhubungan.
3. Buat himpunan
dengan simbol yang dihilangkan dan yang tidak.
Contoh :
1.
S
→
AB
A → abB | aCa | ε
B → bA | BB | ε
C → ε
Jawab :
§
Langkah Pertama
Hilangkan produksi ε pada C → ε
Sehingga menjadi :
S → AB
A → abB | aa | ε
B → bA | BB | ε
§
Langkah Kedua
Hilangkan produksi ε pada B → bA | BB | ε
Sebenarnya disini bebas ingin menghilangkan ε pada A → abB | aa | ε
atau B
→
bA
| BB | ε. Tetapi saya lebih
memilih menghilangkan pada B → bA | BB | ε
Terlebih dahulu.
Sehingga menjadi :
S → AB | A
A → abB | aa | ab | ε
B → bA | BB | B
§ Langkah Ketiga
Hilangkan produksi ε pada A → abB | aa | ε.
Sehingga menjadi :
S → AB | A | B
A → abB | aa | ab
B → bA | BB | B | b
§ Maka hasil akhir penyederhanaan empty dari soal
diatas adalah :
S → AB | A | B
A → abB | aa | ab
B → bA | BB | B | b
2. S → aBCD
| bb | A | ε
A → CDa |
ef
B → b |
Af | ε
C → BbC |
ea
D → ε
Jawab :
§ Langkah Pertama
Hilangkan produksi ε pada D → ε
Sehingga menjadi :
S → aBC | bb | A | ε
A → Ca | ef
B → b | Af | ε
C → BbC | ea
§ Langkah Kedua
Hilangkan produksi ε pada B → b | Af | ε
Sehingga menjadi :
S → aBC | bb | A | aC | ε
A → Ca | ef
B → b | Af
C → BbC | ea | bC
§ Langkah Ketiga
Hilangkan produksi ε pada S → aBC | bb | A | aC | ε
Sehingga menjadi :
S → aBC | bb | A | aC
A → Ca | ef
B → b | Af
C → BbC | ea | bC
§ Maka aasil akhir penyederhanaan produksi empty dari
soal diatas adalah :
S → aBC | bb | A | aC
A → Ca | ef
B → b | Af
C → BbC | ea | bC
d.
Penyederhanaan Produksi Kompleks
Penyederhanaan ini
adalah gabungan dari penyederhanaan produksi useless, penyederhanaan produksi
unit dan penyederhanaan produksi ε (empty).
Langkah penyederhanaan
produksi kompleks :
1.
Lakukan
penyederhanaan produksi ε (empty) terlebih dahulu.
2.
Kemudian, lakukan
penyederhanaan produksi unit.
3.
Terakhir,
lakukan penyederhanaan useless.
Contoh :
1.
S → BACa
B → AC
A → dC | ε
C → D | ε
D → d
Jawab :
§ Langkah Pertama
(Lakukan Penyederhanaan Produksi Empty)
Hilangkan produksi ε pada C → D | ε
Sehingga menjadi :
S → BACa |
BAa
B → AC | A
A → dC | d | ε
C → D
D → d
Hilangkan produksi ε pada A → dC | ε
Sehingga menjadi :
S → BACa |
BAa | BCa | Ba
B → AC | A | C | ε
A → dC | d
C → D
D → d
Hilangkan produksi ε pada B → AC | A | C | ε
Sehingga menjadi :
S → BACa | BAa
| BCa | Ba | ACa | Aa | Ca | a
B → AC | A | C
A → dC | d
C → D
D → d
§ Langkah Kedua
(Lakukan Penyederhanaan Produksi Unit)
Ubah C → D menjadi C → d
Sehingga menjadi :
S → BACa |
BAa | BCa | Ba | ACa | Aa | Ca | a
B → AC | A | C
A → dC | d
C → d
D → d
Ubah B → A menjadi B → dC | d
Sehingga menjadi :
S → BACa |
BAa | BCa | Ba | ACa | Aa | Ca | a
B → AC | dC | d | C
A → dC | d
C → d
D → d
Ubah B → C menjadi B → d
Sehingga menjadi :
S → BACa |
BAa | BCa | Ba | ACa | Aa | Ca | a
B → AC | dC |
d
A → dC | d
C → d
D → d
§ Langkah Ketiga
(Lakukan Penyederhaan Produksi Useless)
Hilangkan D → d karena redundan
Sehingga menjadi
S → BACa |
BAa | BCa | Ba | ACa | Aa | Ca | a
B → AC | dC | d
A → dC | d
C → d
§ Maka hasil akhir penyederhanaan kompleks dari soal
diatas adalah :
S → BACa |
BAa | BCa | Ba | ACa | Aa | Ca | a
B → AC | dC |
d
A → dC | d
C → d
Mohon maaf bila ada kesalahan pada video saya, sekian dan terimakasih
Nama : Shania Risky Agustin
Kelas : 4C
NPM : 1810631170097
Mohon maaf bila ada kesalahan pada video saya, sekian dan terimakasih
Nama : Shania Risky Agustin
Kelas : 4C
NPM : 1810631170097
Tidak ada komentar:
Posting Komentar