PENYEDERHANAAN TATA BAHASA BEBAS KONTEKS
Definisi tata bahasa konteks bebas (CFG) memungkinkan kita untuk mengembangkan berbagai macam tata bahasa. Sebagian besar waktu, beberapa produksi CFG tidak berguna dan berlebihan. Ini terjadi karena definisi CFG tidak membatasi kita untuk membuat produksi yang berlebihan ini.
Tujuan dari penyederhanaan adalah melakukan pembatasan sehingga tidak menghasilkan pohon penurunan yang memiliki kerumitan yang tidak perlu atau aturan produksi yang tidak berarti.
Cara penyederhanaan Tata Bahasa Bebas Konteks dibagi menjadi 3, yaitu:
- Penghilangan produksi useless (tidak berguna).
- Penghilangan produksi unit.
- Penghilangan produksi epsilon (empty).
Penghilangan Produksi Useless
Simbol dapat menjadi tidak berguna jika tidak muncul di sisi kanan aturan produksi dan tidak ikut serta dalam derivasi string apa pun. Simbol itu dikenal sebagai simbol yang tidak berguna.
Produksi useless didefinisikan sebagai:
- Produksi yang memuat simbol variable yang tidak memiliki penurunan yang menghasilkan terminal-terminal seluruhnya.
- Produksi yang tidak pernah dicapai dengan penurunan apapun dari simbol awan, sehingga produksi itu redundan (berlebih).
Contoh penyelesaian 1:
S → aB | C
B → e | Ab
C → bCb | adF | ab
F → cFB
- B → e | Ab (A tidak punya penurunan)
- F → cFB (F tidak punya penurunan ke terminal)
- C → bCb | adF | ab (F tidak punya penurunan)
Hasil penyederhanaan:
S → aB | C
B → e
C → bCb | ab
Contoh penyelesaian 2:
S → Aa | B
A → ab | D
B → b | E
C → bb
E → aEa
- A → ab | D (D tidak punya penurunan)
- C → bb (redundan)
- E → aEa (E tidak punya penurunan ke terminal)
- B → b | E (E tidak punya penurunan)
Hasil penyederhanaan:
S → Aa | B
A → ab
B → b
Penghilangan Produksi Unit
Produksi unit adalah produksi di mana satu non-terminal memberikan non-terminal lain.
Produksi Unit didefinisikan sebagai:
- Produksi dimana ruas kiri dan kanan aturan produksi hanya berupa satu variable, misalkan: A → B, C → D.
- Keberadaannya membuat tata bahasa memiliki kerumitan yang tak perlu.
- Penyederhanaan dilakukan dengan melakukan penggantian aturan produksi unit.
Contoh penyelesaian 1:
S → Aa | B
B → A | bb
A → a | bc | B
Kita jabarkan masing-masing variable supaya nyaman dibaca lalu kita hilangkan produksi unit berurutan mulai dari aturan produksi yang paling dekat menuju terminal-terminal. Hasilnya seperti berikut:
S → Aa
S → B > a | bc | bb
B → A > a | bc
B → bb
A → a
A → bc
A → B > a | bc | bb
Hasil penyederhanaan:
S → A | a | bc | bb
B → a | bc | bb
A → a | bc | bb
Contoh penyelesaian 2:
S → A | Aa
A → B
B → C | b
C → D | ab
D → b
Kita jabarkan dahulu supaya mudah dibaca:
S → A > b | ab
S → Aa
A → B > b | ab
B → C > b | ab
B → b
C → D > b
C → ab
D → b
Hasil penyederhanaan:
S → b | ab | Aa
A → b | ab
B → b | ab
C → b | ab
D → b
Penghilangan Produksi Epsilon (Empty)
Produksi tipe S → ε disebut produksi ε. Jenis produksi ini hanya dapat dihapus dari tata bahasa yang tidak menghasilkan ε. Penghilangan produksi ε dilakukan dengan melakukan penggantian produksi yang memuat varible yang bisa menuju produksi ε, atau biasa disebut nullable.
Ada dua cara untuk menghilangkan Produksi Epsilon, yaitu:
Untuk satu-satunya aturan produksi. Contoh:
S → bcAd
A → ε
Karena ε pada aturan produksi A merupakan satu-satunya aturan produksi, maka variable A pada aturan produksi S menjadi String kosong (atau tidak perlu dituliskan/dihapus). Hasilnya akan seperti berikut:
S → bcd
Bukan satu-satunya aturan produksi. Contoh:
S → bcAd
A → bd | ε
Karena ε pada aturan produksi A bukan satu-satunya aturan produksi (karena dia menghasilkan produksi bd) maka variable A pada S tetap dituliskan, namun kita tambahkan aturan produksi lagi untuk memberikan kemungkinan bahwa A nanti akan menjadi String kosong. Hasilnya akan seperti berikut:
S → bcAd | bcd
A → bd
Contoh penyelesaian 1:
S → AB
A → abB | aCa | ε
B → bA | BB | ε
C → ε
Menghilangkan aturan produksi C:
S → AB
A → abB | aa | ε
B → bA | BB | ε
Menghilangkan aturan produksi B:
S → AB | A
A → abB | ab | aa | ε
B → bA | B | BB
Menghilangkan aturan produksi A dan hasil penyederhanaannya akan seperti berikut:
S → AB | A | B
A → abB | ab | aa
B → bA | b | B | BB
Contoh penyelesain 2:
S → aBCD | bb | A | ε
A → CDa | ef
B → b | Af | ε
C → Bbc | ea
D → ε
Menghilangkan aturan produksi D:
S → aBC | bb | A | ε
A → Ca | ef
B → b | Af | ε
C → Bbc | ea
Menghilangkan aturan produksi B:
S → aBC | ac | bb | A | ε
A → Ca | ef
B → b | Af
C → Bbc | bc | ea
Menghilangkan aturan produksi S dan hasilnya seperti berikut:
S → aBC | ac | bb | A
A → Ca | ef
B → b | Af
C → Bbc | bc | ea
Contoh Menghilangkan Produksi dari ketiga-tiganya (empty, unit, useless)
S → BACa
B → AC
A → dC | ε
C → D | ε
D → d
- Menghilangkan produksi empty
Menghilangkan aturan produksi C:
S → BACa | BAa
B → AC | A
A → dC | d | ε
C → D
D → d
Menghilangkan aturan produksi A:
S → BACa | BAa Bca | Ba
B → AC | A | C
A → dC | d
C → D
D → d
- Menghilangkan produksi unit
Kita jabarkan dahulu ruas kiri dan ruas kanan yang masing-masing memiliki satu variable.
S → BACa | BAa Bca | Ba
B → AC
B → A > dC | d
B → C > d
A → dC
A → d
C → D > d
D → d
Hasil penyederhanaan:
S → BACa | BAa Bca | Ba
B → AC | dC | d
A → dC | d
C → d
D → d
- Menghilangkan produksi useless
D → d (redundan)
Hasil akhir penyederhanaan tata bahasa bebas konteks:
S → BACa | BAa Bca | Ba
B → AC | dC | d
A → dC | d
C → d
Berikut adalah Video penjelasan lengkap mengenai Penyederhanaan Tata Bahasa Bebas Konteks
Daftar Pustaka
Geeks for Geeks. 2018. Simplifying Context Free Grammars. di https://www.geeksforgeeks.org/simplifying-context-free-grammars/ (diakses tanggal 9 April 2020)
Java Point. Simplification of CFG. https://www.javatpoint.com/automata-simplification-of-cfg (diakses tanggal 9 Maret 2020)
Dlan's Tech 