penyederhanaan tata bahasa bebas konteks

PENYEDERHANAAN TATA BAHASA BEBAS

KONTEKSTEORI BAHASA DAN OTOMATA

Melakukan pembatasan sehingga tidak menghasilkan pohon penurunan yang memiliki kerumitan yang tak perlu atau aturan produksi yang tidak berarti.contoh :S AB | aA aKelemahannya : aturan produksi AB menjadi tidak berarti karena B tidak memiliki penurunan.

TUJUAN PENYEDERHANAAN

Suatu tata bahasa bebas konteks dapat disederhanakan dengan melakukan cara berikut ini :1. Penghilangan produksi useless2. Penghilangan produksi unit3. Penghilangan produksi ℰ

Produksi useless adalah : Produksi yang memuat simbol variabel yang

tidak memiliki penurunan yang akan menghasilkan terminal-terminal seluruhnya.

Produksi yang tidak akan pernah dicapai dengan penurunan apapun dari simbol awal.

Penghilangan Produksi Useless

Contoh :S aSa | Abd | BdeA AdaB BBB | aDapat disimpulkan :

1. Simbol variabel A tidak memiliki penurunan yang menuju terminal.

2. Konsekuensi dari no (1), aturan S Abd tidak memiliki penurunan

Maka tata bahasa bebas konteks setelah disederhanakan menjadi :S aSa | BdeB BBB | a

Produksi unit adalah produksi dimana ruas kiri dan kanan aturan produksi hanya berupa satu simbol variabel, misalkan A B, C DContoh :S SbS CC DC efD dd

Penghilangan Produksi Unit

Kita lakukan penggantian berurutan mulai dari aturan produksi paling dekat menuju terminal- terminalC D C ddS C S dd | efsehingga aturan produksi setelah penyederhanaan :S SbS dd | efC ddC efD dd

Produksi ℰ adalah produksi dalam bentuk𝜶 𝜺atau bisa dianggap sebagai produksi kosong.

Penghilangan produksi 𝜺 dilakukan dengan penggantian produksi yang memuat variabel yang bisa menuju produksi 𝜺 atau biasa disebut nullable.

Penghilangan Produksi ℰ

Contoh :S bcAdA 𝜺Pada kasus diatas A nullable, maka variabel A bisa ditiadakan.Hasil penyederhanaanS bcd

Contoh :S bcAd | bcdA bd | 𝜺Hasil penyederhanaanS bcAd | bcdA bd

Alur penyederhanaan Tata Bahasa Bebas Konteks

Contoh :S AA | C |bd

A Bb | 𝜺B AB | dC deSederhanakan.