Tugas 5 : Latihan Penyederhanaan Tata Bahasa Bebas Konteks
Halo...
Pada kesempatan kali ini saya akan membahas latihan dari tugas 5 tentang penyederhanaan tata bahasa bebas konteks baik dengan menggunakan cara penghilangan produksi useless, penghilangan produksi unit, penghilangan produksi empty(ε), dan latihan kompleks.
Penyederhanaan dengan penghilangan produksi useless
Soal latihan 1
S → aB | C
B → e | Ab
C → bCb | adF | ab
F → cFB
B → e | Ab
C → bCb | adF | ab
F → cFB
Jawab :
B → Ab (A tidak punya penurunan)
C → adF (F tidak punya penurunan)
F → cFB (F tidak punya penurunan yang menuju simbol terminal)
C → adF (F tidak punya penurunan)
F → cFB (F tidak punya penurunan yang menuju simbol terminal)
Jadi, setelah disederhanakan :
S → aB | C
B → e
C → bCb | ab
Soal Latihan 2
S → Aa | B
A → ab | D
B → b | E
C → bb
E → aEa
A → ab | D
B → b | E
C → bb
E → aEa
Jawab :
A → D (A tidak punya penurunan)
C → bb (C → bb adalah redudant)
C → bb (C → bb adalah redudant)
Simbol variabel E tidak memiliki aturan produksi menuju terminal
E → aEa (E tidak punya penurunan ke terminal)
E → aEa (E tidak punya penurunan ke terminal)
B → E ( E tidak punya penurunan)
Jadi, setelah disederhanakan :
S → Aa | B
A → ab
B → b
B → b
Penyederhanaan dengan penghilangan produksi unit
Soal Latihan 1
S → Aa | B
B→ A | bb
A → a | bc | B
Jawab :
Penggantian yang dilakukan
A → B menjadi A → bb
B →
A menjadi B → a | bc
S → B menjadi S → a | bc | bb
S → B menjadi S → a | bc | bb
Jadi, setelah disederhanakan :
S → Aa | a | bc
| bb
B → a | bc | bb
B → a | bc | bb
A →
a | bc | bb
Soal Latihan 2
S →
A | Aa
A→ B
B → C | b
C → D | ab
D → b
Jawab :
Pengganti yang dilakukan
C → D menjadi C → b
A → B menjadi A → ab | b
B →
C menjadi B → b | ab
S →
A menjadi S → ab | b
Jadi, setelah disederhanakan :
S → b | Aa | ab
A → b | ab
B →
ab | b
C →
b | ab
D →
b
Penyederhanaan dengan penghilangan produksi empty (ε)
Soal Latihan 1
S → AB
A → abB | aCa
| ε
B → bA | BB
| ε
C → ε
Jawab :
Penghilangan produksi empty (ε)
S → AB menjadi S → AB | A | B
A → abB menjadi A → abB | ab
A → aCa menjadi A → aa
B → bA menjadi B → bA | b
B → BB menjadi B → BB | B
B → ε , A → ε , C → ε dihapus
Jadi, setelah disederhanakan :
S → AB | A | B
A →
abB | ab | aa
B →
bA | b | BB | B
Soal Latihan 2
S → aBCD | bb | A
| ε
A → CDa | ef
B → b | Af
| ε
C → BbC | ea
D → ε
Jawab :
Penghilangan produksi empty (ε)
Variabel yang
nullable: S,B,D
S → ε , B → ε , D → ε dihapus
A → CDa |
ef menjadi A → Ca | ef
S → aBCD | bb | A | ε menjadi S → aBC
| bb | A | ε
C → BbC |
ea menjadi C → BbC | bC| ea
S → aBC | bb | A | ε menjadi S → aBC
| aC | bb | A | ε
S → aBC | aC |
bb | A
Jadi, setelah disederhanakan :
S → aBC | aC |
bb | A
A →
Ca | ef
B →
b | Af
C →
BbC | bC | ea
Latihan Kompleks
Lakukan
penyederhanaan pada himpunan produksi berikut dengan penghilangan empty +
unit + useless sekaligus.
S → BACa
B → AC
A → dC | ε
C → D | ε
D → d
Untuk menjawab soal latihan
kompleks diatas kita harus mengerjakannya sesuai dengan urutan
penyederhanaan tata bahasa bebas konteks. Pertama menghilangkan produksi
empty(ε), kemudian menghilangkan produksi unit, dan terakhir menghilangkan
produksi useless.
Penghilangan produksi empty(ε):
Jawab :
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:
Jawab :
C → D menjadi C →
d
B → A menjadi B → dC | d
B → C menjadi B → d
Maka:
S → BACa |BAa | BCa
B → AC | dC | d
A → dC | d
C → d
D → d
Penghilangan produksi useless:
Jawab :
D → d (D → d adalah redudant)
Jadi, hasil akhir penyederhanaannya adalah:
S → BACa |BAa | BCa
B → AC | dC | d
A → dC | d
C → d
Untuk lebih jelasnya dapat melihat video pembahasan penyederhanaan tata bahasa bebas konteks dibawah ini
aokwoakoakwokaowkaokwkawokaowkwkkwkwk
ReplyDeletePELIK PELIK
ReplyDelete