TUGAS Materi 5
Latihan Penyederhanaan Tata Bahasa Bebas Konteks
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
Komentar
Posting Komentar