PENYEDERHANAAN CFG

1. TUJUAN PENYEDERHANAAN

• Melakukan pembatasan sehingga tidak menghasilkan pohon penurunan yang memiliki kerumitan yang tidak perlu atau aturan produksi yang tidak berarti.

• Contoh :

S 􀃆 AB | a

A 􀃆 a

Kelemahan CFG diatas, aturan produksi S 􀃆 AB tidak berarti karena B tidak memiliki penurunan.

Untuk CFG berikut :

S 􀃆 A

A 􀃆 B

B 􀃆 C

C 􀃆 D

D 􀃆 a | A

Memiliki kelemahan terlalu panjang jalannya padahal berujung pada S 􀃆 a, produksi D 􀃆 A juga menyebabkan kerumitan.

• Suatu CFG dapat disederhanakan dengan melakukan :

1. Penghilangan produksi useless (tidak berguna)

2. Penghilangan produksi unit

3. Penghilangan produksi ε

2. PENGHILANGAN PRODUKSI USELESS

• Produksi useless didefinisikan sebagai :

- Produksi yang memuat simbol variabel yang tidak memiliki penurunan yang akan menghasilkan terminal-terminal seluruhnya (disebut ‘menuju terminal’). Produksi ini tidak berguna karena bila diturunkan tidak akan pernah selesai masih ada simbol variabel yang tersisa.

- Produksi yang tidak akan pernah dicapai dengan penurunan apapun dari simbol awal sehingga produksi itu redundance (berlebih)

• Contoh terdapat CFG :

S 􀃆 aSa | Abd | Bde

A 􀃆 Ada

B 􀃆 BBB | a

Maka :

1. Simbol variabel A tidak memiliki penurunan yang menuju terminal, sehingga bisa dihilangkan

2. Konsekuensi no. (1), aturan produksi S 􀃆 Abd tidak memiliki penurunan maka CFG setelah disederhanakan menjadi :

S 􀃆 aSa | Bde

B 􀃆 BBB | a

• Contoh terdapat CFG :

S 􀃆 Aa | B

A 􀃆 ab | D

B 􀃆 b | E

C 􀃆 bb

E 􀃆 aEa

Maka :

1. Pada aturan produksi A 􀃆 D, simbol variabel D tidak memiliki penurunan

2. Pada aturan produksi C 􀃆 bb, bila dicoba melakukan penurunan dari simbol awal S tidak akan pernah mencapai C.

3. Simbol variabel E tidak memiliki aturan produksi yang menuju terminal

24

4. Konsekuensi no (3) aturan produksi B 􀃆 E, simbol variabel E tidak memiliki penurunan

Sehingga dari CFG diatas, produksi yang useless :

A 􀃆 D

C 􀃆 bb

E 􀃆 aEa

B 􀃆 E

Maka CFG setelah disederhanakan menjadi :

S 􀃆 Aa | B

A 􀃆 ab

B 􀃆 b

• Contoh CFG :

S 􀃆 aAb | Ceb

A 􀃆 Dbe | eeC

B 􀃆 ff

C 􀃆 ae

D 􀃆 h

Maka :

1. Pada aturan produksi S 􀃆 Ceb, A 􀃆 Dbe (E tidak memiliki penurunan)

2. Aturan produksi D 􀃆 h redundan

Sehingga :

S 􀃆 aAb

A 􀃆 eeC

B 􀃆 ff

C 􀃆 ae

Dari sisa CFG diatas B 􀃆 ff juga redundan, sehingga hasil penyederhanaan menjadi :

S 􀃆 aAb

A 􀃆 eeC

C 􀃆 ae

• Contoh CFG :

S 􀃆 Ab

A 􀃆 bcD | Dac

B 􀃆 e | Ab

C 􀃆 bCb | adF | ab

F 􀃆 Cfb

Maka :

1. Pada aturan produksi A 􀃆 bcD, variabel D tidak memiliki penurunan

2. Konsekuensi no (1), simbol variabel A tidak memiliki penurunan yang menuju terminal sehingga tersisa hanya A 􀃆 Dac

3. Konsekuensi no (2), B 􀃆 Ab tidak memiliki penurunan

4. Simbol variabel F tidak memiliki penurunan yang menuju terminal

5. Konsekuensi no (4), C 􀃆 adF tidak memiliki penurunan

Setelah disederhanakan menjadi :

S 􀃆 Ab

B 􀃆 e

• Contoh CFG :

S 􀃆 Abd

B 􀃆 Cd | Ab

D 􀃆 ef

A 􀃆 Ed

F 􀃆 dc

Maka :

1. Pada aturan produksi A 􀃆 Ed, E tidak memiliki penurunan

2. Pada aturan produksi F 􀃆 dc, redundan

25

Sehingga :

S 􀃆 Abd

B 􀃆 Cd | Ab

D 􀃆 ef

Dari sisa CFG diatas maka pada aturan produksi B 􀃆 Ab, A tidak mempunyai penurunan, sehingga aturan produksi setelah disederhanakan :

S 􀃆 Abd

B 􀃆 Cd

D 􀃆 ef

• Contoh CFG :

S 􀃆 Abc | ab

A􀃆 AAA | ε

Maka :

S 􀃆 Abc | ab

A􀃆 AAA | ε

Hasil tetap karena A 􀃆 ε diperhitungkan.

• Prinsipnya setiap kali melakukan penyederhanaan, periksa lagi aturan produksi yang tersisa, apakah semua produksi yang useless sudah dihilangkan.

2. PENGHILANGAN PRODUKSI UNIT

• Produksi unit adalah produksi dimana ruas kiri dan kanan aturan produksi hanya berupa satu simbol variabel, misalkan A 􀃆 B, C 􀃆 D

• Keberadaan produksi unit membuat tata bahasa memiliki kerumitan yang tidak perlu atau menambah panjang penurunan.

• Penyederhanaan ini dilakukan dengan melakukan penggantian aturan produksi unit

• Contoh CFG :

S 􀃆 Sb

S 􀃆 C

C 􀃆 D

C 􀃆 ef

D 􀃆 dd

Lakukan penggantian berturutan mulai dari aturan produksi yang oaling dekat menuju ke penurunan terminal.

C 􀃆 D menjadi C 􀃆 dd

S 􀃆 C menjadi S 􀃆 dd | ef

Sehingga aturan produksi setelah penyederhanaan :

S 􀃆 Sb

S 􀃆 dd | ef

C 􀃆 dd

C 􀃆 ef

D 􀃆 dd

• Contoh CFG

S 􀃆 A

S 􀃆 Aa

A 􀃆 B

B 􀃆 C

B 􀃆 b

C 􀃆 D

C 􀃆 ab

D 􀃆 b

26

Penggantian yang dilakukan :

C 􀃆 D menjadi C 􀃆 b

B 􀃆 C menjadi B 􀃆 b | ab karena B 􀃆 b sudah ada maka cukup tulis B 􀃆 ab

A 􀃆 B menjadi A 􀃆 ab | b

S 􀃆 A menjadi S 􀃆 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

• Contoh CFG

S 􀃆 Cba | D

A 􀃆 bbC

B 􀃆 Sc | ddd

C 􀃆 Ea | f | C

D 􀃆 E | SABC

E 􀃆 gh

Penggantian yang dilakukan :

D 􀃆 E menjadi D 􀃆 gh

C 􀃆 C dihapus

S 􀃆 D menjadi S 􀃆 gh | SABC

Sehingga aturan produksi setelah penyederhanaan :

S 􀃆 Cba | gh | SABC

A 􀃆 bbC

B 􀃆 Sc | ddd

C 􀃆 Ea | f

D 􀃆 gh | SABC

E 􀃆 gh

3. PENGHILANGAN PRODUKSI ε

• Produksi ε adalah produksi dalam bentuk α 􀃆 ε atau bisa dianggap sebagai produksi kosong (empty).

• Penghilangan ε dilakukan dengan penggantian produksi yang memuat variabel yang bisa menuju produksi ε atau disebut nullable.

• Contoh :

S 􀃆 bcAd

A 􀃆 ε

Pada kasus diatas A nullable, serta A 􀃆 ε satu-satunya produksi dari A, maka variabel A bisa ditiadakan . Hasil penyederhanaan CFG menjadi :

S 􀃆 bcd

Tetapi bila kasusnya :

S 􀃆 bcAd

A 􀃆 bd | ε

Pada kasus diatas A nullable tapi A 􀃆 ε bukan satu-satunya produksi dari A, maka hasil penyederhanaan :

S 􀃆 bcAd | bcd

A 􀃆 bd

27

• Contoh CFG :

S 􀃆 Ab | Cd

A 􀃆 d

C 􀃆 ε

Variabel yang nullable adalah variabel C. Karena penurunan C 􀃆 ε merupakan penurunan satu-satunya dari C, maka produksi C 􀃆 ε dihapus dan S 􀃆 Cd menjadi S 􀃆 d.

Hasil penyederhanaan CFG :

S 􀃆 Ab | d

A 􀃆 d

• Contoh CFG :

S 􀃆 Da | Bd

A 􀃆 bc

A 􀃆 ε

B 􀃆 C

Variabel yang nullable adalah variabel A.

A 􀃆 ε bukan penurunan satu-satunya dari A (terdapat A 􀃆 bc), maka

S 􀃆 Da menjadi S 􀃆 Da | d dan A 􀃆 ε dihapus.

Setelah penyederhanaan :

S 􀃆 Da | d | Bd

A 􀃆 bc

B 􀃆 c

• Contoh CFG :

S 􀃆 AaCD

A 􀃆 CD | AB

B 􀃆 b | ε

C 􀃆 d | ε

D 􀃆 ε

Variabel yang nullable adalah variabel B,C,D.

Dari A 􀃆 CD, D hanya memiliki penurunan D 􀃆 ε,maka D 􀃆 ε dihapus sehingga

S 􀃆 AaCD menjadi S 􀃆 AaC

A 􀃆 CD menjadi A 􀃆 C

Variabel B dan C memiliki penurunan ε meskipun bukan satu-satunya penurunan maka dilakukan penggantian :

A 􀃆 AB menjadi A 􀃆 AB | A | B

S 􀃆 AaC menjadi S 􀃆 AaC | Ac | Aa | a

B 􀃆 ε dan C 􀃆 ε dihapus

Setelah penyederhanaan :

S 􀃆 AaC | Ac | Aa | a

A 􀃆 C | AB | A | B

B 􀃆 b

C 􀃆 d

• Contoh CFG :

S 􀃆 AB

A 􀃆 abB | aCa | ε

B 􀃆 Ba | BB | ε

C 􀃆 ε

Variabel yang nullable adalah A,B,C.

Dari S 􀃆 AB, maka S juga nullable. Lakukan penggantian :

A 􀃆 aCa menjadi A 􀃆 aa

28

B 􀃆 Ba menjadi B 􀃆 Ba | b

B 􀃆 BB menjadi B 􀃆 BB | B

A 􀃆 abB menjadi A 􀃆 abB | ab

S 􀃆 AB menjadi S 􀃆 AB | A | B | ε

C 􀃆 ε, B 􀃆 ε, A 􀃆 ε dihapus

Perhatikan :

Untuk penggantian S 􀃆 AB, S 􀃆 ε tetap dipertahankan karena S merupakan simbol awal. Ini merupakan satu-satunya perkecualian produksi ε yang tidak dihapus yaitu produksi ε yang dihasilkan oleh simbol awal.

Hasil akhir penyedernaan :

S 􀃆 AB | A | B | ε

A 􀃆 abB | ab | aa

B 􀃆 Ba | b | BB | B

• Contoh CFG :

S 􀃆 aAb

A 􀃆 aAb | ε

Hasil penyederhanaan :

S 􀃆 aAb | ab

A 􀃆 aAb | ab

• Contoh CFG :

S 􀃆 ABaC

A 􀃆 BC

B 􀃆 b | ε

C 􀃆 D | ε

D 􀃆 d

Hasil penyederhanaan :

S 􀃆 ABaC | BaC | AaC | ABa | aC | Aa | Ba | a

A 􀃆 B | C | BC

B 􀃆 b

C 􀃆 D

D 􀃆 d

• Pada prakteknya ketiga penyederhanaan tersebut (penghilangan useless, unit, ε) dilakukan bersama pada suatu CFG yang nantinya menyiapkan CFG tersebut untuk diubah ke dalam bentuk normal Chomsky (dibahas bab selanjutnya).

• Hal yang memerlukan perhatian adalah penghilangan suatu tipe produksi bisa menghasilkan produksi yang lain, hal ini didasari kenyataan bahwa penghilangan suatu tipe produksi bisa menghasilkan produksi tipe yang lain, hal ini didasari kenyataan bahwa penghilangan produksi ε bisa menghasilkan produksi unit.

• Tapi perhatikan juga bahwa penghilangan produksi unit tidak menghasilkan produksi ε dan penghilangan produksi useless tidak menghasilkan produksi unit maupun produksi ε.

• Maka untuk menghapus semua produksi yang tidak diinginkan tersebut dengan melakukan urutan sebagai berikut :

1. Hilangkan produksi ε

2. Hilangkan produksi unit

3. Hilangkan produksi useless

CFG yang sudah disederhanakan

Penghilangan

produksi useless

Penghilangan

produksi unit

Penghilangan

produksi ε

CFG

• Hasil yang diperoleh adalah tata bahasa yang sudah bebas dari ketiga jenis produksi tersebut.

Contoh :

29

S 􀃆 AA | C | bd

A 􀃆 Bb | ε

B 􀃆 AB | d

C 􀃆 de

Lakukan penghilangan produksi ε, sehingga aturan produksi menjadi :

S 􀃆 A | AA | C | bd

A 􀃆 Bb

B 􀃆 B | AB | d

C 􀃆 de

Penghilangan produksi ε berpotensi untuk menghasilkan produksi unit baru yang sebelumnya tidak ada. Selanjutnya lakukan penghilangan produksi unit menjadi :

S 􀃆 Bb | AA | de | bd

A 􀃆 Bb

B 􀃆 AB | d

C 􀃆 de

Penghilangan produksi unit bisa menghasilkan produksi useless sehingga lakukan penghilangan produksi useless :

S 􀃆 Bb | AA | de | bd

A 􀃆 Bb

B 􀃆 AB | d

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