Nama : Muhammad Diki Hendriyanto
Kelas : 4G
NPM : 181063117199
Pada kesempatan kali ini saya akan membahas latihan dari penyederhanaan tata bahasa bebas konteks baik dengan menggunakan cara penghilangan produksi useless, penghilangan produksi unit, maupun penghilangan produksi empty(ε).
1. Penyederhanaan dengan penghilangan produksi useless
Untuk menjawab soal latihan penyederhanaan dengan penghilangan produksi useless kita harus menghapus aturan produksi yang tidak memiliki penurunan dan juga aturan produksi yang berlebih atau redudan.
S → aB | C
B → e | Ab
C → bCb | adF | ab
F → cFB
- 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
Soal Latihan 2
S → Aa | B
A → ab | D
B → b | E
C → bb
E → aEa
- 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
A → ab
B → b
2. Penyederhanaan dengan penghilangan produksi unit
Untuk menjawab soal latihan penyederhanan dengan penghilangan produksi unit(produksi di mana ruas kiri dan kanan hanya terdapat satu simbol variabel) yaitu dengan cara penggantian produksi unit berurutan mulai dari aturan produksi yang paling dekat ke terminal.
S → Aa | B
B→ A | bb
A → a | bc | B
- Analisa penghilangan produksi unit:
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
Soal Latihan 2
S → A | Aa
A→ BB → C | b
C → D | ab
D → b
- Analisa penghilangan produksi unit:
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
3. Penyederhanaan dengan penghilangan produksi empty (ε)
Untuk menjawab soal latihan penyederhanaan dengan penghilangan produksi empty yaitu dengan cara melakukan penggantian produksi yang nullable.
S → AB
A → abB | aCa | ε
B → bA | BB | ε
C → ε
- Analisa penghilangan produksi empty(ε):
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
Soal Latihan 2
S → aBCD | bb | A | ε
A → CDa | ef
B → b | Af | ε
C → BbC | ea
D → ε
- Analisa penghilangan produksi empty(ε):
Variabel yang nullable: S,B,D, maka:
D → ε (dihapus), maka
A → CDa | ef ==> A → Ca | ef
S → aBCD | bb | A | ε ==> S → aBC | bb | A | ε
B → ε (dihapus), maka
C → BbC | ea ==> C → BbC | bC| ea
S → aBC | bb | A | ε ==> S → aBC | aC | bb | A | ε
S → ε (dihapus), maka
S → aBC | aC | bb | A
- Hasil Penyederhanaan:
S → aBC | aC | bb | A
A → Ca | ef
B → b | Af
C → BbC | bC | ea
4. Latihan Kompleks
Lakukan penyederhanaan pada himpunan produksi berikut dengan penghilangan empty +
unit + useless sekaligus.
S → BACaunit + useless sekaligus.
B → AC
A → dC | ε
C → D | ε
D → d
Untuk menjawab soal latihan kompleks diatas saya harus mengerjakannya sesuai urutan penyederhanaan tata bahasa bebas konteks. Pertama menghilangkan produksi empty(ε), setelah itu menghilangkan produksi unit, dan terakhir menghilangkan produksi useless.
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 → dB → 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
Untuk lebih jelasnya silahkan lihat video pembahasan penyederhanaan tata bahasa bebas konteks di bawah ini
Sekian pembahasan latihan soal tentang penyederhanaan tata bahasa bebas konteks, semoga bermanfaat bagi para pembaca dan maaf bila ada kesalahan karena saya bukan manusia yang sempurna.
Wassalamualaikum Wr. Wb.
Daftar Pustaka:
Materi 5 Tata Bahasa Bebas Konteks (Penyederhaan Tata Bahasa Bebas Konteks) [pdf]. Dosen pengampu: Garno, M.Kom. Fakultas Ilmu Komputer Universitas Singaperbangsa Karawang.
EmoticonEmoticon