Teori Bahasa dan Automata - Penyederhanaan Tata Bahasa Bebas Konteks

TUJUAN PENYEDERHANAAN

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

Langkah-langkah penyederhanaan dari tata bahasa bebeas konteks ini adalah dengan cara:

1.      Menghilangkan Produksi yang useless (tidak berguna)

2.      Menghilangkan produk unit

3.      Menghilangkan produk ε

1. Menghilangkan Produksi Uselees

Produksi Uselees didefinisikan sebagai berikut :

·                     Produksi yang memuat symbol variable yang tidak memiliki penurunan yang akan menghasilkan terminal-terminal seluruhnya

·                     Produksi yang tidak akan pernah dicapai dengan penurunan apapun dari symbol awal, sehingga produk itu redudan.

Contoh:

Terdapat aturan produksi sebagai berikut :

S → aBD

B → cD | Ab

D → ef

A → Ed

F → dc

Analisa :

1)      Pada aturan produksi A → Ed , E tidak memiliki penurunan. Sehingga dapat dihilangkan

2)      Aturan produksi F → dc, redudan. Sehingga aturan produksi tersebut dapat dihilangkan

3)      Aturan produksi B → Ab, A tidak memiliki penurunan. Sehingga didapat penyederhanaan.

Maka hasil akhirnya:

            S → aBD

            B → cD

            D → ef

Kesimpulannya adalah bahwa produk usselees yang dihilangkan adalah:

            A → Ed

            F → dc

B → Ab 

2.  Menghilangkan Produksi Unit

Produk 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 kw 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. Menghilangkan Produksi ε

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

Penghilangan produksi  ε dilakukan dengan melakukan penggantian produksi yang memuat variable yang bias 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

Video tentang penjelasan teknik-teknik penyederhanaan dengan contoh soal :