penyederhanaan cfg

TEORI BAHASA &

AUTOMATA

PENYEDERHANAA

N

CFG

Penyederhanaan CFG

Tujuannya : Untuk melakukan

pembatasan sehingga tidak

menghasilkan pohon penurunan yg

memiliki kerumitan yg tdk perlu / aturan

produksi yg tdk berarti.

Contoh :

•S→ AB | a

A → a

Aturan S→ AB tdk berarti krn B tdk

memiliki penurunan

Contoh

•S → A

A → B

B → C

C → D

D → a | A

Memiliki kelemahan yaitu terlalu panjang jlnnya padahal berujung pd S → a, D → A juga menyebabkan kerumitan.

Suatu tata bahasa bebas konteks (CFG)

dpt

disederhanakan dgn melakukan :

1.Penghilangan produksi useless

2.Penghilangan produksi unit

3.Penghilangan produksi ε

Penghilangan Produksi

Useless

Produksi Useless :

•Produksi yg memuat simbol variabel yg tdk

memiliki penurunan yg akan menghasilkan

terminal2 seluruhnya, produksi ini tdk

berguna krn bl diturunkan tdk akan pernah

selesai (msh ada simbol variabel yg tersisa)

•Produksi yg tdk akan pernah dicapai dgn

penurunan apapun dr simbol awal, shg

produksi itu redundan (berlebih)

Contoh 1 :

S → aSa | Abd | Bde

A → Ada

B → BBB | a

•Simbol A tdk memiliki penurunan yg

menuju terminal, shg bisa dihilangkan

•Konsekuensi no 1, aturan produksi S →

Abd tdk memiliki penurunan

Bentuk sederhana :

S → aSa | Bde

B → BBB | a

Prinsipnya setiap kali melakukan

penyederhanan kita periksa lagi aturan

produksi yg tersisa, apakah semua

produksi yg useless sdh dihilangkan.

Contoh 2 :

S → aBA → bcD | dACB → e | AbC → bCb | adF | abF → cFBLangkah penyederhanaan :1.A → bCD, D tdk memiliki penurunan2.Konsekuensi no1, A tdk memiliki penurunan yg

menuju terminal 3.B → Ab tdk memiliki penurunan4.F tdk memiliki penurunan yg menuju terminal5.C → adF tdk memiliki penurunan6.C tdk pernah dijumpai dipenurunan manapun

Shg menjadi :

S → aB

B → e

Penghilangan Produksi Unit

Produksi unit adalah produksi dmn ruas kiri dan kanan aturan produksi hanya berupa satu simbol variabel, misalnya : A → B, C → D.

Keberadaan produksi unit membuat tata bahasa memiliki kerumitan yg tdk perlu atau menambah panjang penurunan.

Penyederhanaan ini dilakukan dgn melakukan penggantian aturan produksi.

Contoh 1 :

S → Sb

S → C

C → D

C → ef

D → dd

Kita lakukan penggantian berturutan mulai dari

aturan produksi yg paling dekat menuju ke

penurunan terminal2 ( ‘=>’ dibaca ‘menjadi’)

C → D => C → dd

S → C => S → dd | ef

Shg disederhanakan mjd :

S → Sb

S → dd | ef

C → dd

C → ef

D → dd

Contoh 2 :

S → Cba | D

A → bbC

B → Sc | ddd

C → eA | f | C

D → E | SABC

E → gh

Penggantian yg dilakukan :

D → E => D → gh

C → C dihapus

S → D => S → gh | SABC

Shg aturan produksi setelah

disederhanakan :

S → Cba | gh | SABC

A → bbC

B → Sc | ddd

C → eA | f

D → gh | SABC

E → gh

Penghilangan Produksi ε

Penghilangan produksi ε dilakukan dgn

melakukan penggantian produksi yg memuat

variabel yg bisa menuju produksi ε. Prinsip

penggantiannya bisa dilihat kasus berikut :S → bcAdA → εPada kasus diatas A nullable, serta A → ε satu2nya produksi dari A, mk variabel A bisa ditiadakan, hasil penyederhanaan tata bahasa bebas konteks mjd :S → bcd

Tetapi bila kasusnya :

S → bcAd

A → bd | ε

Pada kasus diatas A nullable, tapi A → ε

bukan satu2nya produksi dari A, mk hasil

penyederhanaan :

S → bcAd | bcd

A → bd

Contoh 1 :S → ABA → abB | aCa | εB → bA | BB | εC → ε Variabel yg nullable A, B, C. Dari S → AB, maka S juganullable. Kita lakukan penggantian :A → aCa => A → aaB → bA => B → bA | bB → BB => B → BB | BA → abB => A → abB | abS → AB => S → AB | A | B | εC → ε, B → ε, A → ε dihapus

Perhatikan : untuk penggantian S → AB

kita tetap mempertahankan produksi S →

ε, krn S merupakan simbol awal. Ini

merupakan satu2nya perkecualian

produksi ε yg tdk dihapus, yaitu produksi

ε yg dihasilkan oleh simbol awal.

Hasil Penyederhanaan

S → AB | A | B | ε

A → abB | ab | aa

B → bA | b | BB | B

Contoh 2 :

S → ABaC

A → BC

B → b | ε

C → D | ε

D → d

Variabel yg nullable B, C. Kita lakukanpenggantian :A → BC => A → BC | B | CS → ABaC => S → ABaC | AaC | BaC | ABa| aC | Aa | Ba | aHasil penyederhanaan :S → ABaC | AaC | BaC | ABa | aC | Aa | Ba | aA → BC | B | CB → bC → DD → d

Penyederhaan CFG

CFGPenghilanga

n

Produksi ε

Penghilanga

n

Produksi

Unit

Penghilangan

Produksi

Useless

CFG yg sdh

disederhanak

an

Latihan 1 :

Lakukan penghilangan aturan produksi unit, useless, dan ε dari tata bahasa bebas konteks berikut :

S → a | aA | B | C

A → aB | ε

B → Aa

C → cCD

D → ddd

Latihan 2 :

Lakukan penghilangan aturan produksi

unit, useless, dan ε dari tata bahasa

bebas konteks berikut :

S → aB | aaB

A → ε

B → bA

B → ε

Jawaban Latihan 1 :Penghilangan Produksi ε :A → ε dihilangkan, shg : A → aBB → Aa | aS → a | aA | B | CMjd :S → a | aA | B | CA → aB B → Aa | aC → cCDD → ddd

Penghilangan Produksi Unit :S → B => S → Aa | aS → C => S → cCDShg menjadi :S → a | aA | Aa | cCDA → aB B → Aa | aC → cCDD → ddd

Penghilangan Produksi Useless :1.C tidak memiliki penurunan, shg C → cCD

dihilangkan2.S → cCD dihilangkan3.Konsekuensi no 2, D → ddd dihilangkan

Shg mjd :S → a | aA | AaA → aBB → Aa | a

Jawaban Latihan 2 :

Penghilangan Produksi ε :A → ε dihilangkan, shg : B → bA => B → bB → ε dihilangkan, shg :S → aB => S → aB | aS → aaB => S → aaB | aaMjd :S → aB | a | aaB | aaB → b

Penghilangan Produksi Unit :

Tidak ada krn semua aturan produksi

tidak ada yang ruas kiri dan kanannya

mempunyai sebuah simbol variabel.

Penghilangan Produksi Useless :

Karena tidak ada yg redundan dan semua

aturan produksinya sdh sederhana, mk

hasil dari penghilangan produksi useless

= hasil dari penghilangan produksi ε