Teknik-Teknik Penyederhanaan Produksi Empty, Produksi Unit dan Produksi useless

Penyederhanaan Tata Bahasa Bebas Konteks

(Context Free Grammar)

CFG atau Context Free Grammar adalah tata bahasa formal di mana setiap aturan produksi adalah dalam bentuk A → B di mana A adalah pemproduksi, dan B adalah hasil produksi. Batasannya hanyalah ruas kiri adalah sebuah simbol variabel. Dan pada ruas kanan bisa berupa terminal, symbol, variable ataupun ɛ, Contoh aturan produksi yang termasuk CFG adalah seperti berikut ini:

·         X → bY | Za

·         Y → aY | b

·         Z → bZ | ɛ

Atau contoh lainnya seperti, diketahui suatu tata bahasa konteks:

·         S → AB | a

·         A → a

Kelemahan : Aturan produksi S → AB tidak berarti karena B tidak memiliki penurunan

CFG adalah tata bahasa yang mempunyai tujuan sama seperti halnya tata bahasa regular yaitu merupakan suatu cara untuk menunjukkan bagaimana menghasilkan suatu untai-untai dalam sebuah bahasa.

CFG perlu disederhankan dengan tujuan untuk melakukan pembatasan sehingga tidak menghasilkan pohon penurunan yang memiliki kerumitan yang tak perlu atau aturan produksi tak berarti. Berikut merupakan langkah-langkah dalam melakukan penyederhanaan CFG:

·         Penghilangan Produksi Useless

·         Penghilangan Produksi Unit

·         Penghilangan Produksi ε

1.      Penghilangan Produksi Useless

Penghilangan Produksi Useless adalah Produksi yang memuat simbol variable yang tidak memiliki penurunan yang akan menghasilkan terminal-terminal seluruhnya (menuju terminal), produksi ini tidak berguna karena bila diturunkan tidak akan pernah selesai (masih ada simbol variable tersisa). Produksi ini tidak akan pernah dicapai dengan penurunan apapun dari simbol awal, sehingga produksi itu redundan (berlebih).

Contoh 1 :

Diketahui tata bahasa bebas konteks sebagai berikut

S → aSa | Abd | Bde

A → Ada

B → BBB | a

Bisa dilihat :

·         Simbol variable A tidak memiliki penurunan yang menuju terminal, sehingga bisa dihilangkan.

·          Konsekuensi no 1, aturan produksi S → Abd tidak memiliki penurunan

Maka tata bahasa hasil penyederhanaan adalah :

S → aSa | Bde

B → BBB | a

Contoh 2 :

Diketahui tata bahasa bebas konteks sebagai berikut

S → Aa | B

A → ab | D

B → b | E

C → bb

E → aEa

Bisa dilihat :

·         Aturan produksi A → D, simbol variable D tidak memiliki penurunan, sehingga bisa dihilangkan.

·          Aturan produksi C → bb, jika dilakukan penurunan dari simbol awal S, dengan jalan manapun tidak akan pernah dicapai. Sehingga bisa dihilangkan.

·         Simbol variable E tidak memiliki aturan produksi yang menuju terminal ( E → aEa ) satu-satunya aturan produksi dari E, sehingga bisa dihilangkan.

·         Konsekuensi no 3, aturan produksi B → E, simbol variable E tidak memiliki penurunan, sehingga bisa dihilangkan.

Dapat dilihat, produksi yang useless adalah :

A → D

C → bb

E → aEa

B → E

Maka tata bahasa hasil penyederhanaan menjadi :

S → Aa | B

A → ab

B → b

Soal Latihan 1

Penyederhanaan dengan penghilangan produksi Useless

S → aB | C

B → e |Ab

C → bCb | adF | ab

F → cFB

Lakukan penyederhanaan produksi useless dengan:

1. Menganalisis Vn yang tidak memiliki turunan atau Vn yang tidak pernah berhenti pada Vt, kemudian hilangkanlah.

2.      Redudant/Berlebih/tidak terjangkau dari start awal.

Jawab :

Maka useless:

S → aB

S → C

B → e

B → Ab    (A tidak punya penurunan )

C → bCb  

C → adF   (F tidak mempunyai penurunan)

C → ab

F → cFB   (F tidak mempunyai penurunan)

Hasil penyederhanaan :

·         S → aB | C

·         B → e

·         C → bCb | ab

Soal Latihan 2

Penyederhanaan dengan penghilangan produksi Useless

S → Aa | B

A → ab | D

B → b | E

C → bb

E → aEa

Lakukan penyederhanaan produksi useless dengan:

1. Menganalisis Vn yang tidak memiliki turunan atau Vn yang tidak pernah berhenti pada Vt, kemudian hilangkanlah.

2. Redudant/Berlebih/tidak terjangkau dari start awal.

Jawab :

Maka useless:

E → aEa (E tidak punya penurunan)

C → bb (penurunan)

B → E (karena E tidak punya penurunan, ,maka B tidak memiliki penurunan juga )

A → D ( tidak punya penurunan)

Hasil penyederhanaan :

·         S → Aa | B

·         A → ab

·         B → b

2.      Penghilangan Produksi Unit

Produksi unit adalah produksi yang ruas kiri dan kanan aturan produksinya hanya berupa satu simbol variable misalkan: A -> B, C -> D. Dengan adanya bentuk prioduksi unit ini membuat tata bahasa memiliki kerumitan yang tidak perlu atau menambah panjang penurunan. Penyederhanaan ini dilakukan dengan melakukan penggantian aturan produksi unit.

Contoh 1:

S -> Sb

S -> C

C -> D

C -> ef

D -> dd

Dilakukan penggantian berturutan mulai dari aturan produksi yang paling dekat menuju ke penurunan terminal-terminal (‘=>’ dibaca ‘menjadi’):

·         C -> D => C -> dd

·         S -> C => S -> dd | ef

Sehingga aturan produksi setelah penyederhanaan:

S -> Sb

S -> dd | ef

C -> dd | ef

Contoh 2 :

S -> A

S -> Aa

A -> B

B -> C

B -> b

C -> D

C ->ab

D -> b

Penggantian yang dilakukan :

• C -> D => C -> b

• B -> C => B -> b | ab, karena B -> b sudah ada, maka cukup dituliskan B -> ab

• A -> B => A -> ab | b

• S -> A => ab | b

Sehingga aturan produksi setelah penyederhanaan:

S -> ab | b

S -> Aa

A -> ab | b

B ->ab

B -> b

C -> b

C -> ab

D -> b

Soal Latihan 1

Penyederhanaan dengan penghilangan produksi Unit

S  → Aa | B

B → A | bb

A → a | bc | B

Lakukan penyederhanaan produksi unit dengan:

1.      Penghilangan pada produksi unit yang ruas kiri dan kanannya satu simbol variable non terminal, dan tidak memiliki turunan.

Jawab:

Produksi unit :

B → A | bb menjadi B → a | bc | B |bb

B → B dihapuskan

S → Aa | B menjadi S → Aa | bc | a | bb

Hasil :

S → Aa | bc | a | bb

B → a | bc | bb

A →  a | bc

Soal Latihan 2

Penyederhanaan dengan penghilangan produksi Unit

S → A | Aa

A → B

B → C | b

C → D | ab

D → b

Lakukan penyederhanaan produksi unit dengan:

1. Penghilangan pada produksi unit yang ruas kiri dan kanannya satu simbol variable non terminal, dan tidak memiliki turunan.

Jawab :

Produksi unit :

C → D menjadi C → b

B → C menjadi b | Ab ditulis B → ab

A → B menjadi A → ab|b

S → A menjadi S → ab|b

Hasil :

S → ab | b                   B → ab                        C → ab

S → Aa                       B → b                         D → b

A → ab | b                   C →b

3.      Penghilangan Produsi Empty (Ɛ)

Produksi ε (Empty) adalah produksi dalam bentuk α Æ ε atau bisa dianggap sebagai produksi kosong. Penghilangan produksi ε dilakukan dengan melakukan penggantian produksi yang memuat variable yang manuju produksi ε, atau bias disebut nullable. Prinsip penggantian bias dilihat kasus berikut :

Kasus 1.

S -> bcAd

A -> ε

Pada kasus 1, A nullable serta A -> ε merupakan satu-satunya produksi dari A maka variable A bias ditiadakan. Maka hasil penyederhanaan adalah : S -> bcd

Kasus 2.

S -> bcAd

A -> bd | ε

Pada kasus 2, A nullable, tapi A -> ε bukan satu-satunya produksi dari A. Maka hasil penyederhanaan adalah : S -> bcAd | bcd A -> bd

Contoh 1 :

Diketahui tata bahasa bebas konteks sebagai berikut :

S -> Ab | Cd

A -> d

C -> ε

Variabel yang nullabel adalah C. karena penurunan C -> ε merupakan penurunan satusatunya dari C, maka kita ganti S -> Cd manjadi S -> d. kemudian produksi C -> ε dihapus.

Tata bahasa bebas konteks setelah penyederhanaan :

S -> Ab | d

A -> d

Contoh 2 :

S -> dA | Bd

A -> bc

A -> ε

B -> c

Variabel yang nullable adalah A, A -> ε bukan satu-satunya produksi dari A. Maka kita ganti S -> dA manjadi S -> dA | d kemudian A -> ε dihapus.

Tata bahasa bebas konteks hasil penyederhanaan :

S -> dA | d | Bd

A -> bc

B -> c

Soal Latihan 1

Penyederhanaan dengan penghilangan produksi Empty (ε)

S → AB

A → abB | aCa | ε

B → bA | BB | ε

C → ε

Lakukan penyederhanaan produksi Empty (ε)  dengan:

1.      Menghilangkan produksi unit yang mengandung ε

Jawab :

Produksi unit :

A, B, C adalah var nullable dari S → AB, maka S = nullable.

S → AB          B → bA         

A → abB         B → BB

A → aCa

C → ε, B → ε, A → ε di hapuskan.

Hasil :

S → Ab | A | B

A →abB| ab | aa

B → ba |b | BB| B

Soal Latihan 2

Penyederhanaan dengan penghilangan produksi Empty (ε)

S → aBCD | bb | A | ε

A → CDa | ef

B → b | Af | ε

C → BbC | ea

D → ε

Lakukan penyederhanaan produksi empty/ε dengan:

1. Menghilangkan produksi unit yang mengandung ε.

Jawab:

S, B, D adalah var nullable, maka

S → Abcd menjadi S → aBC | aC

A → CDa menjadi A → Ca

C → bbC menjadi C → BbC |bC

S → ε, B → ε, D → ε dihapuskan.

Hasil :

S → Abc | aC |bb |A

A → Ca | ef

B → b| Af

C → BbC | bC | ea

4.      Tata Bahasa Bebas Konteks

Prakteknya ketiga penyederhanaan tersebut dilakukan bersama pada suatu tata bahasa bebas konteks, yang nantinya menyiapkan tata bahasa bebas konteks tersebut untuk diubah kedalam suatu bentuk normal Chomsky.

Urutan penghapusan aturan produksi :

1) Hilangkan produksi ε

2) Hilangkan produksi unit

3) Hilangkan produksi useless

Contoh :

S -> AA | C | bd

A -> Bb | ε

B -> AB | d

C -> de

Hilangkan produksi ε, sehingga menjadi:

S -> A | AA | C | bd

A -> Bb

B -> B | AB | d

C -> de

Selanjutnya penghilangan produksi unit menjadi:

S -> Bb | AA | de | bd

A -> Bb

B -> AB | d

C -> de

Penghilangan produksi unit bisa menghasilkan produksi useless.

Terakhir dilakukan penghilangan produksi useless:

S -> Bb | AA | de | bd

A -> Bb

B -> AB | d

Hasil akhir aturan produksi tidak lagi memiliki produksi ε, produksi unit, maupun produksi useless.

Bb | AA | de | bd

A -> Bb

B -> AB | d

Hasil akhir aturan produksi tidak lagi memiliki produksi ε, produksi unit, maupun produksi useless.

Latihan Kompleks

Lakukan penyederhanaan pada himpunan produksi berikut

dengan penghilangan empty+unit+useless sekaligus.

S → BACa

B → AC

A → dC | ε

C → D | ε

D → d

Jawab :

·         Penyederhanaan Empty (ε)

S → BACa

B → AC

A → dC

C → D

D → d

·         Penyedehanaan Unit

S → BACa | Baa | BCa | Ba

B → AC |dC | d

A → dC | d

C → d

D → d

·         Penyederhanaan Useless

S → BACa | Baa | BCa | Ba

B → AC | dC | d

A → dC |d

C → d




daftar pustaka :
- https://repository.unikom.ac.id/45133/1/Penyederhanaan%20Tata%20Bahasa%20Bebas%20Konteks.pdf
- http://herilovemetallica.blogspot.com/2009/10/penyederhanaan-tata-bahasa-dalam-teori.html
- https://socs.binus.ac.id/2018/12/20/penyederhanaan-context-free-grammar/