Penyederhanaan tata bahasa bebas konteks ini memiliki tujuan agar tidak menghasilkan pohon penurunan yang memiliki kerumitan yang tidak diperlukan atau menghilangkan 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 → 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.
Analisa :
B → Ab (A tidak punya penurunan)
C → adF (F tidak punya penurunan)
F → cFB (F tidak punya penurunan ke terminal)
Hasil Penyederhanaan:
S → aB | C
B → e
C → bCb | ab
contoh 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.
Analisa :
A → D (A tidak punya penurunan)
B → E (F tidak punya penurunan)
C → bb (C → bb adalah redudan)
E → aEa (E tidak punya penurunan ke terminal)
Hasil Penyederhanaan:
S → Aa | B
B → ab
C → b
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 → 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.
Analisa :
A → B ==> A → bb
B → A ==> B → a | bc | bb , Karena B → bb sudah ada maka cukup ditulis B → a | bc
S → B ==> S → a | bc | bb
Hasil Penyederhanaan :
S → Aa | a | bc | bb
B → a | bc | bb
A → a | bc | bb
contoh 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.
Analisa :
C → D ==> C → b
B → C ==> B → b | ab , Karena B → b sudah ada maka cukup ditulis B → ab
A → B ==> A → ab | b
S → A ==> S → ab | b
Hasil Penyederhanaan:
S → ab | b | Aa
A → ab | b
B → ab | b
C → b | ab
D → b
Penghilanagan Produksi ε
Produksi ε 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 → AB
A → abB | aCa | ε
B → bA | BB | ε
C → ε
Lakukan penyederhanaan produksi Empty/ε dengan:
1. Menghilangkan produksi unit yang mengandung ε
Analisa :
Variabel yang nullable: A,B,C, maka:
A → ε (dihapus)
Maka, S → AB | B
A → abB | ab | aa
B → b | BB
B → ε (dihapus)
Maka, S → AB | A
B → bA | BB | B
A → abB | ab | aa
C → ε (dihapus)
Maka, A → abB | aa
Hasil Penyederhanaan :
S → AB | A | B
A → abB | ab | aa
B → bA | b | BB | B
Contoh 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 ε.
Analisa :
Variabel yang nullable: S,B,D, maka:
S → ε (dihapus)
B → ε (dihapus)
D → ε (dihapus)
Hasil Penyederhanaan:
S → aBC | aC | bb | A
A → Ca | ef
B → b | Af
C → BbC | bC | ea
Latihan Kompleks
penyederhanaan pada himpunan produksi berikut
dengan penghilangan empty+unit+useless sekaligus.
S → BACa
B → AC
A →dC | ε
C → D | ε
D → d
Penghilangan produksi empty(ε) :
Analisa:
Variabel yang nullable: A,C, maka:
A → ε (dihapus)
C → ε (dihapus)
Maka:
S → BACa |BAa | BCa
B → AC | A | C
A → dC | d
C → D
D → d
Penghilangan produksi unit :
Analisa:
C → D ==> C → d
B → A ==> B → dC | d
B → C ==> B → d
Maka:
S → BACa |BAa | BCa
B → AC | dC | d
A → dC | d
C → d
D → d
Penghilangan produksi useless:
Analisa:
D → d (D → d adalah redudan)
Hasil Akhir Penyederhanaan :
S → BACa |BAa | BCa
B → AC | dC | d
A → dC | d
C → d
berikut adalah penjelasan video mengenai contoh soal diatas :
https://drive.google.com/file/d/1ajR4zJaeQbgGf-QLjsdkWiUHhwAGrQeG/view?usp=sharing
https://drive.google.com/file/d/1ajR4zJaeQbgGf-QLjsdkWiUHhwAGrQeG/view?usp=sharing
Tidak ada komentar:
Posting Komentar