Materi Penyederhanaan Tata Bahasa Bebas Konteks

Assalamualaikum Wr. Wb.

Dalam artikel kali ini saya akan menjelaskan tentang penyederhanaan tata bahasa bebas konteks dengan menggunakan cara penghilangan produksi useless(tidak berguna).

Penyederhanaan Tata Bahasa Bebas Konteks (CFG)

Penyederhanaan tata bahasa bebas konteks ini memiliki tujuan agar tidak menghasilkan pohon penurunan yang memiliki kerumitan yang tidak diperlukan atau menghilangkan produksi yang tidak berarti.

Langkah-langkah penyederhanaan dari tata bahasa bebas konteks ini adalah dengan cara sebagai berikut:

Penghilangkan Produksi yang useless (tidak berguna)
Penghilangkan Produksi unit
Penghilangkan Produksi ε

1. Penghilangan Produksi Useless

Produksi Useless didefinisikan sebagai berikut :

Produksi yang memuat simbol variable yang tidak memiliki penurunan yang akan menghasilkan terminal-terminal seluruhnya
Produksi yang tidak akan pernah dicapai dengan penurunan apapun dari simbol awal, sehingga produk itu redudan.

Contoh:

Terdapat aturan produksi sebagai berikut :

S → aBD

B → cD | Ab

D → ef

A → Ed

F → dc

Analisa :

Pada aturan produksi A → Ed , E tidak memiliki penurunan. Sehingga dapat dihilangkan.
Aturan produksi F → dc, redudan. Sehingga aturan produksi tersebut dapat dihilangkan.
Aturan produksi B → Ab, A tidak memiliki penurunan. Sehingga dapat dihilangkan.

Maka hasil akhirnya:

S → aBD

B → cD

D → ef

Kesimpulannya adalah bahwa produk useless yang dihilangkan adalah:

A → Ed

F → dc

B → Ab

2. Penghilangan Produksi Unit

Produksi Unit adalah produksi dimana ruas kiri dan kanan aturan produksi hanya berupa satu simbol variabel. Contoh A → B, atau C → D

Keberadaan produksi unit ini membuat tata bahasa memiliki kerumitan yang tak perlu. Untuk menyederhanakan produksi unit, dilakukan penggantian aturan produksi unit tersebut.

Contoh :

Diberikan aturan produksi sebagai berikut :

S → A

S → Aa

A → B

B → C

B → b

C → D

C → ab

D → b

Lakukan penggantian berurutan mulai dari aturan produksi yang paling dekat menuju ke penurunan terminal-terminal (“=>” dibaca”menjadi”)

C → D => C → b

B → C => B → b | ab, karena B → b sudah ada maka cukup ditulis B → ab

A → B => A → ab | b

S → A => S → ab | b

Sehingga aturan produksi yang telah disederhanakan dengan menghilangkan produksi unit adalah sebagai berikut :

S → ab | b

S → Aa

A → ab | b

B → ab

B → b

C → b

C → ab

D → b

3. Penghilangan Produksi Empty (ε)

Produksi ε adalah produksi dalam bentuk α → ε atau bisa dianggap sebagai produksi kosong (empty).

Penghilangan produksi ε dilakukan dengan melakukan penggantian produksi yang memuat variable yang bisa menuju produksi ε, atau disebut juga Nullable.

Contoh :

Terdapat tata bahasa bebas konteks sebagai berikut :

S → aB | Cd

A → d

C → ε

Variabel yang nullable adalah variable C, karena penurunan C → ε merupakan penurunan satu-satunya dari C, maka kita ganti S → Cd menjadi S → d, kemudian produksi C → ε kita hapus.

Maka hasil penyederhanaannya adalah :

S → aB | d

A → d

Alur Penyederhanaan Tata Bahasa Bebas Konteks

Sekian 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(ε).

Wassalamualaikum Wr. Wb.

Daftar Pustaka:
Materi 5 Tata Bahasa Bebas Konteks (Penyederhaan Tata Bahasa Bebas Konteks) [pdf]. Dosen pengampu: Garno, M.Kom. Fakultas Ilmu Komputer Universitas Singaperbangsa Karawang.
https://fairuzelsaid.wordpress.com/2011/06/16/penyederhanaan-context-free-grammar-cfg/
http://teoribahasa.blogspot.com/2014/01/teori-bahasa-automata.html

Diki-H©2021

Materi Penyederhanaan Tata Bahasa Bebas Konteks

Artikel Menarik Lainnya