PENYEDERHANAAN TATA BAHASA BEBAS KONTEK
Teori Bahasa dan Automata
Penyederhanaan Tata Bahasa Bebas Kontek
Tujuan Penyederhanaan :
Tujuan dari penyederhanaan adalah melakukan pembatasan sehingga tidak menghasilkan pohon penurunan yang memiliki kerumitan yang tak perlu atau memotong aturan produksi yang tidak perlu.
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 Empty / (ε) Epsilon
1. 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
Terdapat aturan produksi sebagai berikut :
S --> aB | C
B --> e | Ab
C --> bCb | adF | ab
F --> cFB
Maka produksi yang useless beserta analisanya :
1. B --> Ab (Aturan produksi B --> Ab, A tidak mempunyai penurunan. Maka dapat dihapus)
2. F --> cFB (Simbol variabel F tidak memiliki penurunan yang menuju ke terminal . Maka dapat dihapuskan).
3. C --> adF (Konsekuensi no (2) aturan produksi C --> adF tidak memiliki penurunan. Maka dapat dihapus).
Sehingga didapat hasil penyederhanaan :
S --> aB | C
B --> e
C --> bCb | ab
Contoh 2
Terdapat aturan produksi sebagai berikut :
S --> Aa | B
A --> ab | D
B --> b | E
C --> bb
E --> aEa
Maka produksi yang useless beserta analisanya :
1. A --> (Pada aturan produksi A --> D, D tidak memiliki penurunan. Maka dapat dihapus).
2. C --> bb (Aturan produksi C --> bb merupakan redundan, karena penurunan dari symbol S dengan jalan manapun tidak akan pernah mencapai C. Maka dapat dihapus).
3. E --> aEa (Pada symbol variabel E tidak memiliki penurunan yang menuju ke terminal. Maka dapat dihapuskan).
4. B --> E (Konsekuensi pada no (3) aturan produksi B --> E tidak memiliki penurunan. Maka dapat dihapus).
Sehingga didapat hasil penyederhanaan :
S --> Aa | B
A --> ab
B --> b
2. Penghilangan Produksi Unit
- Produksi unit merupakan suatu produksi dimana ruas kiri dan ruas kanan aturan produksi hanya berupa satu symbol variabel, misalkan F --> N
- Penyederhanaan dilakukan dengan melakukan penggantian aturan produksi unit.
- Penggantian produksi unit dapat dilakukan dengan berurutan mulai dari aturan produksi yang paling dekat menuju ke penurunan terminal.
Contoh 1
Terdapat aturan produksi sebagai berikut :
S --> Aa | B
B --> A | bb
A --> a | bc | B
Penggantian yang dilakukan ('=>' dibaca 'menjadi') :
B --> A => B --> a | bc | bb
A --> B => A --> a | bc | bb
S --> B => S --> a | bc | bb
Aturan produksi setelah penyederhaan :
S --> Aa | a | bc | bb
B --> a | bc | bb
A --> a | bc | bb
Contoh 2
Terdapat aturan produksi sebagai berikut :
S --> A | Aa
A --> B
B --> C | b
C --> D | ab
D --> b
Penggantian yang dilakukan ('=>' dibaca 'menjadi') :
C --> D => C --> b
B --> C => B --> b | ab
A --> B => A --> b | ab
S --> A => S --> b | ab
Aturan produksi setelah penyederhanaan :
S --> b | ab | Aa
A --> b | ab
B --> b | ab
C --> b | ab
D --> b
3. Penghilangan Produksi Epsilon (ε)
- Produksi ε merupakan produksi
dalam bentuk a --> ε atau bisa dianggap sebagai
produksi kosong.
- Penghilangan produksi ε dapat
dilakukan dengan penggantian produksi yang memuat variabel yang bisa menuju
produksi ε atau
bisa disebut nullable.
- Prinsip penggantiannya
bisa dilihat dengan contoh :
S --> Abc
A --> ε
A nullable, serta
A --> ε merupakan
satu - satunya produksi dari A. Maka variabel A dapat dihapuskan. Hasil
penyederhanaannya menjadi :
S --> bc
Tetapi bila kasusnya :
S --> Abc
A --> cd | ε
Dimana A nullable tetapi
A --> ε satu - satunya produksi
dari A. Maka hasil penyederhanaannya menjadi :
S --> Abc | bc
A --> cd
Contoh 1
Terdapat aturan
produksi sebagai berikut :
S --> AB
A --> abB |
aCa | ε
B --> bA | BB | ε
C --> ε
Hilangkan C --> ε terlebih dahulu, maka hasilnya :
S --> AB
A --> abB |
aa | ε
B --> bA | BB | ε
Hilangkan ε yang ada di B, maka hasilnya :
S --> AB | A
A --> abB | aa | bb | ε
B --> bA | BB
Hilangkan ε yang ada pada A, maka hasil akhirnya akan
seperti ini :
S --> AB | A |
B
A --> abB | aa
| ab
B --> bA | BB |
b
Contoh 2
Terdapat aturan
produksi sebagai berikut :
S --> aBCD |
bb | A | ε
A --> CDa | ef
B --> b | Af | ε
C --> BbC | ea
D --> ε
Hilangkan D --> ε terlebih dahulu dengan cara menghapus
semua D yang ada pada aturan produksi, maka hasilnya :
S --> aBC | bb
| A | ε
A --> Ca | ef
B --> b | Af | ε
C --> BbC | ea
Hilangkan ε yang ada pada
B, dengan cara mengganti B menjadi string kosong, maka hasilnya :
S --> aBC | BB
| A | aC | ε
A --> Ca | ef
B --> b | Af
C --> Bbc | ea
| bc
Hingga hasil
penyelesaiannya seperti ini :
S --> aBC | bb
| A | aC
A --> Ca | ef
B --> b | Af
C --> Bbc | ea
| bc
Latihan Soal Komplek
- Untuk soal komplek, kita harus
mengerjakannya secara berututan, mulai dari Epsilon (ε), Unit, dan Useless.
Terdapat aturan
produksi sebagai berikut :
S -->
BACa
B --> AC
A -->
dC | ε
C --> D | ε
D --> d
Petama, penghilangan
produksi epsilon dengan cara, hilangkan ε yang ada pada
C, maka hasilnya :
S --> BACa |
BAa | BCa | ACa | Aa | Ca | Ba | a
B --> AC | A |
C
A --> dC | d
C --> D
D --> d
Kedua, penghilangan
produksi unit, dengan cara mencari yang paling dekat dengan penurunan ke
terminal yaitu D --> d. Maka hasilnya :
S --> BACa | BAa | BCa
| ACa | Aa | Ca | Ba | a
B --> AC | dC |
d
A --> dC | d
C --> d
D --> d
Ketiga, penghilangan
produksi useless, dengan
cara menghapus D --> d karena D itu redundan dan tidak akan ada yang menuju
ke terminal D. Maka hasil akhirnya seperti ini :
S --> BACa | BAa | BCa
| ACa | Aa | Ca | Ba | a
B --> AC | dC |
d
A --> dC | d
C --> d
Video Penjelasan Penyederhanaan Bebas Kontek
Comments
Post a Comment