PENYEDERHANAAN TATA BAHASA BEBAS KONTEKS

Halo...

Dalam artikel kali ini saya akan menjelaskan tentang penyederhanaan tata bahasa bebas konteks. Apa itu bahasa bebas konteks ? Apa itu tata bahasa bebas konteks ? Bagaimana penyederhanaan tata bahasa bebas konteks ? 
Mari kita bahas dibawah ini

Pengertian :

Bahasa Bebas Konteks (CRF) adalah sebuah tata bahasa dimana tidak terdapat pembatasan pada hasil produksinya. Contoh pada aturan produksi : a → b

Tata bahasa bebas konteks (CFG) adalah tata bahasa yang mempunyai tujuan sama seperti halnya tata bahasa regular yaitu merupakan suatu cara untuk menujukan bagaimana menghasilkan suatu untai-untai dalam suatu bahasa

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

Contoh :
S → AB | a
S → a

  

Kelemahannya : aturan produksi AB menjadi tidak berarti karena B tidak memiliki penurunan.

Ada 3 bentuk penyederhanaan : 

1. Penghilangan produksi useless

2. Penghilangan produksi unit

3. Penghilangan produksi ε

Penghilangan Produksi Useless

Definisi Penghilangan Produksi useless adalah : 

• Produksi yang memuat simbol variabel yang tidak memiliki penurunan yang akan menghasilkan terminal-terminal seluruhnya (masih ada simbol variabel yang tersisa) 

• Produksi yang tidak akan pernah dicapai dengan penurunan apapun dari simbol awal sehingga produksi itu redundan(berlebih).

Contoh :

S → aSa | Abd | Bde

A → Ada
B → BBB | a

C → h

Dapat disimpulkan :

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

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

3. C → h adalah redundan

Setelah penyederhanaan menjadi :

S → aSa | Bde

B → BBB | a

Contoh :

S → Aa | B

A → ab | D

B → b | EC → bbE → aEa

Maka :

1. Aturan produksi A → D, simbol variabel D tidak memiliki penurunan.

2. Aturan produksi C → bb, penurunan dari simbol dengan jalan manapun tidak akan pernah mencapai C.

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

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

maka produksi yang useless:

A → D

C → bb

E → aEa

B → E

Penyederhanaan menjadi :

S → Aa | B

A → ab

B → b

Penghilangan Produksi Unit

Definisi Penghilangan Produksi Unit:

• Produksi unit adalah produksi dimana ruas kiri dan kanan aturan produksi hanya berupa satu simbol variabel, 

misalkan A → B, C → D.

Contoh :

S → Sb

S → C

C → D

C → ef

D → dd

Melakukan penggantian berurutan mulai dari aturan produksi yang paling terdekat menuju terminal - 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

Penghilangan Produksi ε

Definisi Penghilangan Produksi ε
• Produksi ε adalah produksi dalam bentuk α → ε atau biasa dianggap sebagai produksi kosong(empty)
•  Penghilangan produksi ε dilakukan dengan melakukan penggantian produksi yang memuat variabel yang bisa menuju produksi ε atau biasa disebut nullable.

Contoh :
S → aB | Cd
A → d
C → ε
*pada kasus diatas C nullable, maka variabel C bisa ditiadakan. Penurunan C → ε merupakan penurunan satu - satunya dari C, maka S → Cd menjadi S → d. Produksi C → ε bisa dihapus.

Hasil Penyederhanaan :
S → aB | d
A → d

Gabungan Useless, Unit, dan ε

Ketiga penyederhanaan ini dilakukan secara bersamaan pada suatu tata bahasa konteks, yang nantinya tata bahasa konteks ini diubah ke dalam bentuk normal Chomsky (CNF).
Urutannya sebagai berikut :

1. Hilangkan produksi ε
2. Hilangkan produksi unit
3. Hilangkan produksi useless

Contoh :
Hilangkan produksi useless, unit, dan empty dari tata bahasa konteks berikut :
S → a | aA | B | C
A → aB | ε
C → cCD
D → ddd

Jawab :
1. Penghilangan produksi ε

2. Penghilangan produksi unit

3. Penghilangan produksi useless

Demikian artikel saya kali ini semoga bermanfaat bagi pembaca dan dapat memahami tentang penyederhanaan tata bahasa bebas konteks dengan cara penghilangan produksi useless, penghilangan produksi unit, dan penghilangan produksi empty(ε).


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/