Tata Bahasa Bebas Konteks (CFG)

Pengertian

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

Batasan hanyalah ruas kri (a) adalah sebuah symbol variable. Sedangkan contoh aturan produksi yang termasuk CFG adalah sebagai berikut:

B → cDeFg

D → BcDe

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

Penyederhanaan Tata Bahasa Bebas Konteks (CFG)

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 ε

Apa yang dimaksud dengan produksi uselees, produk unit dan produk ε ? dan bagaimana cara menghilangkanya :

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