penyederhanaan tata bahasa bebas konteks
DESCRIPTION
PENYEDERHANAAN TATA BAHASA BEBAS KONTEKS. TEORI BAHASA DAN OTOMATA. TUJUAN PENYEDERHANAAN. Melakukan pembatasan sehingga tidak menghasilkan pohon penurunan yang memiliki kerumitan yang tak perlu atau aturan produksi yang tidak berarti . contoh : S AB | a A a - PowerPoint PPT PresentationTRANSCRIPT
![Page 1: PENYEDERHANAAN TATA BAHASA BEBAS KONTEKS](https://reader036.vdokumen.com/reader036/viewer/2022082316/56814bbf550346895db894c4/html5/thumbnails/1.jpg)
PENYEDERHANAAN TATA BAHASA BEBAS
KONTEKSTEORI BAHASA DAN OTOMATA
![Page 2: PENYEDERHANAAN TATA BAHASA BEBAS KONTEKS](https://reader036.vdokumen.com/reader036/viewer/2022082316/56814bbf550346895db894c4/html5/thumbnails/2.jpg)
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
![Page 3: PENYEDERHANAAN TATA BAHASA BEBAS KONTEKS](https://reader036.vdokumen.com/reader036/viewer/2022082316/56814bbf550346895db894c4/html5/thumbnails/3.jpg)
Suatu tata bahasa bebas konteks dapat disederhanakan dengan melakukan cara berikut ini :1. Penghilangan produksi useless2. Penghilangan produksi unit3. Penghilangan produksi ℰ
![Page 4: PENYEDERHANAAN TATA BAHASA BEBAS KONTEKS](https://reader036.vdokumen.com/reader036/viewer/2022082316/56814bbf550346895db894c4/html5/thumbnails/4.jpg)
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
![Page 5: PENYEDERHANAAN TATA BAHASA BEBAS KONTEKS](https://reader036.vdokumen.com/reader036/viewer/2022082316/56814bbf550346895db894c4/html5/thumbnails/5.jpg)
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
![Page 6: PENYEDERHANAAN TATA BAHASA BEBAS KONTEKS](https://reader036.vdokumen.com/reader036/viewer/2022082316/56814bbf550346895db894c4/html5/thumbnails/6.jpg)
Maka tata bahasa bebas konteks setelah disederhanakan menjadi :S aSa | BdeB BBB | a
![Page 7: PENYEDERHANAAN TATA BAHASA BEBAS KONTEKS](https://reader036.vdokumen.com/reader036/viewer/2022082316/56814bbf550346895db894c4/html5/thumbnails/7.jpg)
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
![Page 8: PENYEDERHANAAN TATA BAHASA BEBAS KONTEKS](https://reader036.vdokumen.com/reader036/viewer/2022082316/56814bbf550346895db894c4/html5/thumbnails/8.jpg)
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
![Page 9: PENYEDERHANAAN TATA BAHASA BEBAS KONTEKS](https://reader036.vdokumen.com/reader036/viewer/2022082316/56814bbf550346895db894c4/html5/thumbnails/9.jpg)
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 ℰ
![Page 10: PENYEDERHANAAN TATA BAHASA BEBAS KONTEKS](https://reader036.vdokumen.com/reader036/viewer/2022082316/56814bbf550346895db894c4/html5/thumbnails/10.jpg)
Contoh :S bcAdA 𝜺Pada kasus diatas A nullable, maka variabel A bisa ditiadakan.Hasil penyederhanaanS bcd
![Page 11: PENYEDERHANAAN TATA BAHASA BEBAS KONTEKS](https://reader036.vdokumen.com/reader036/viewer/2022082316/56814bbf550346895db894c4/html5/thumbnails/11.jpg)
Contoh :S bcAd | bcdA bd | 𝜺Hasil penyederhanaanS bcAd | bcdA bd
![Page 12: PENYEDERHANAAN TATA BAHASA BEBAS KONTEKS](https://reader036.vdokumen.com/reader036/viewer/2022082316/56814bbf550346895db894c4/html5/thumbnails/12.jpg)
Alur penyederhanaan Tata Bahasa Bebas Konteks
![Page 13: PENYEDERHANAAN TATA BAHASA BEBAS KONTEKS](https://reader036.vdokumen.com/reader036/viewer/2022082316/56814bbf550346895db894c4/html5/thumbnails/13.jpg)
Contoh :S AA | C |bd
A Bb | 𝜺B AB | dC deSederhanakan.