Penyederhanaan tata bahasa bebas dapat dilakukan dengan cara

Pada kesempatan kali ini saya akan membahas latihan dari tugas 5 tentang penyederhanaan tata bahasa bebas konteks baik dengan menggunakan cara penghilangan produksi useless, penghilangan produksi unit, penghilangan produksi empty(ε), dan latihan kompleks.

Penyederhanaan dengan penghilangan produksi useless

S → aB | C
B → e | Ab
C → bCb | adF | ab
F → cFB

B → Ab (A tidak punya penurunan)
C → adF (F tidak punya penurunan)
F → cFB (F tidak punya penurunan yang menuju simbol terminal)

Jadi, setelah disederhanakan :
S → aB | C
B → e

S → Aa | B
A → ab | D
B → b | E
C → bb
E → aEa

A → D (A tidak punya penurunan)
C → bb (C → bb adalah redudant)

Simbol variabel E tidak memiliki aturan produksi menuju terminal
E → aEa (E tidak punya penurunan ke terminal)

B → E ( E tidak punya penurunan)

Jadi, setelah disederhanakan :

Penyederhanaan dengan penghilangan produksi unit

Penggantian yang dilakukan

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

Jadi, setelah disederhanakan :

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

Jadi, setelah disederhanakan :

Penyederhanaan dengan penghilangan produksi empty (ε)

Penghilangan produksi empty (ε)

S → AB menjadi S → AB | A | B

A → abB menjadi A → abB | ab

B → bA menjadi B → bA | b

B → BB menjadi B → BB | B

B → ε , A → ε , C → ε dihapus

Jadi, setelah disederhanakan :

Penghilangan produksi empty (ε)

Variabel yang nullable: S,B,D

S → ε , B → ε , D → ε dihapus

A → CDa | ef menjadi A → Ca | ef

S → aBCD | bb | A | ε menjadi S → aBC | bb | A | ε

C → BbC | ea menjadi C → BbC | bC| ea

S → aBC | bb | A | ε menjadi S → aBC | aC | bb | A | ε

Jadi, setelah disederhanakan :

Lakukan penyederhanaan pada himpunan produksi berikut dengan penghilangan empty +

unit + useless sekaligus.

Untuk menjawab soal latihan kompleks diatas kita harus mengerjakannya sesuai dengan urutan penyederhanaan tata bahasa bebas konteks. Pertama menghilangkan produksi empty(ε), kemudian menghilangkan produksi unit, dan terakhir menghilangkan produksi useless.

Penghilangan produksi empty(ε):

Variabel yang nullable: A,C, maka:

Penghilangan produksi unit:

Penghilangan produksi useless:

D → d (D → d adalah redudant)

Jadi, hasil akhir penyederhanaannya adalah:

C → d

Untuk lebih jelasnya dapat melihat video pembahasan penyederhanaan tata bahasa bebas konteks dibawah ini

Daftar Pustaka : Materi Persentasi "Penyederhaan Tata Bahasa Bebas Konteks" Dosen pengampu Teori Bahasa Automata: Garno, M.Kom. Fakultas Ilmu Komputer Universitas Singaperbangsa Karawang https://docplayer.info/45902166-Penyederhanaan-tata-bahasa-bebas-konteks-kuliah-online-tba-2012-2013.html http://teoribahasa.blogspot.com/2014/01/teori-bahasa-automata.html https://kikifaradilla.wordpress.com/2015/03/20/tata-bahasa-bebas-konteks-teori-bahasa-automata/

Tata bahasa bebas kompleks (Context Free Grammar) merupakan sebuah tata bahasa dimana tidak terdapat pembatasan pada hasil produksinya. Contoh pada aturan produksi :α → β

Batasannya hanyalah ruas kiri (α) adalah sebuah variabel non terminal.

Penyederhanaan tata bahasa bebas konteks bertujuan untuk melakukan sehingga tidak menghasilkan pohon penurunan yang memiliki kerumitan yang tidak perlu atau aturan produksi yang tidak berarti.
Suatu tata bahasa bebas konteks dapat melakukan penyederhanaan dengan melakukan cara :

Penghilangan produksi Useless
Penghilangan produksi Unit
Penghilangan produksi ε

Penghilangan Produksi Useless

Definisi 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 variabel tersisa). Dan juga produksi Useless memiliki definisi lain yaitu produksi yang tidak akan pernah dicapai dengan penurunan apapun dari simbol awal, sehingga produksi itu redundan (berlebih).

Contoh :Diketahui tata bahasa bebas konteks sebagai berikut :S → Aa | BA → ab | DB → b | EC → bbE → aEaAnalisis :1. Aturan produksi A → D, variabel D tidak memiliki penurunan, sehingga bisa dihilangkan.2. Aturan produksi C → bb, jika dilakukan dengan penurunan dari simbol awal S, dengan jalan mana pun tidak akan pernah tercapai. Sehingga bisa dihilangkan.3. Simbol variabel E tidak memiliki aturan produksi yang menuju terminal, sehingga bisa dihilangkan.4. Konsekuensi no. 3, aturan produksi B → E, simbol variabel E tidak memiliki penurunan, sehingga bisa dihilangkan.Maka tata bahasa hasil penyederhanaannya menjadi :S → Aa | BA → ab

B → b

Penghilangan Produksi Unit

Produksi unit adalah produksi yang ruas kanan dan ruas kirinya memiliki aturan produksi hanya berupa satu simbol variabel. Penyederhanaan ini dilakukan dengan melakukan penggantian aturan produksi unit.Contoh :Diketahui tata bahasa bebas konteks sebagai berikut :S → SbS → CC → DC → efD → ddAnalisis :Lakukan penggantian berurutan mulai dari aturan produksi yang paling dekat menuju terminal-terminal.C → D menjadi C → ddS → C menjadi S → dd | efHasil penyederhanaan :S → Sb | dd | efC → dd | ef

D → dd

Penghilangan Produksi Empty (ε)

Penghilangan produksi empty adalah :
• Produksi ε (Empty) adalah produksi dalam bentuk α → ε atau bisa dianggap produksi kosong.
• Penghilangan produksi empty dilakukan dengan melakukan penggantian produksi yang memuat variabel yang menuju produksi ε, atau biasa disebut nullable.Contoh :Diketahui tata bahasa bebas konteks sebagai berikut :S → dA | BdA → bcA → εB → cAnalisis :1. A → ε dihapus karna menghasilkan ε2. S → dA berubah menjadi S → dA | dHasil penyederhanaan :S → dA | d | BdA → bc

B → c

Gabungan Useless, Unit dan Empty

Urutan penyederhanaan dari gabungan useless, unit, dan empty, yaitu :

Gambar 1 Tahapan penyederhanaan

Tahap 1 : Penghilangan produksi empty

A → ε dihapus karena A menghasilkan produksi kosong.

Hasil penyederhanaan/penghilangan produksi empty :

S → a | aA | B | CA → aBB → Aa | aC → cCDD → dddTahap 2 : Penghilangan produksi UnitS → B diubah menjadi S → AaS → C diubah menjadi S → cCD

Hasil penyederhanaan/penghilangan produksi unit dan empty :

S → a | aA | Aa | cCDA → aBB → Aa | aC → cCDD → ddd

Tahap 3 : Penghilangan produksi useless

C → cCD dihapus karena redundanS → cCD dihapusD → ddd dihapus karena tidak ada penurunan di simbol awal

Hasil penyederhanaan/penghilangan produksi empty, unit dan useless :

S → a | aA | Aa

A → aB | a

Itulah penjelasan tentang penyederhanaan tata bahasa bebas kompleks. Berikut adalah video penjelasan latihan penyederhanaan tata bahasa bebas kompleks.

Referensi :
https://repository.unikom.ac.id/45133/1/Penyederhanaan%20Tata%20Bahasa%20Bebas%20Konteks.pdf
https://www.scribd.com/doc/293082099/8-Penyederhanaan-Tata-Bahasa-Bebas-Konteks
https://slideplayer.info/slide/12678996/