Teori Bahasa dan Automata - Tata Bahasa Bebas Konteks (Teknik Penyederhanaan)

Dibuat Oleh pada

TATA BAHASA BEBAS KONTEKS


 Assalamualaikum Wr. Wb.

Pada postingan ini saya akan membagikan sebuah materi penyederhanaan tata bahasa bebas konteks. Tujuan saya membuat postingan ini adalah untuk memenuhi Tugas Materi 5 pada Mata Perkuliahan TEORI BAHASA DAN AUTOMATA.


Penyederhanaan Tata Bahasa Bebas Konteks (CFG) bertujuan untuk melakukan pembatasan sehingga tidak menghasilkan pohon penurunan yang memiliki kerumitan yang tidak perlu atau aturan produksi yang tidak berarti.

Contoh
Diketahui suatu tata bahasa konteks seperti berikut:

            S → AB | a

          A → a

Kelemahan:
Aturan Produksi S --> AB tidak berarti karena B tidak memiliki penurunan

 Berikut adalah langkah-langkah Penyederhanaan Tata Bahasa Bebas Konteks (CFG):

1. Penghilangan Produksi Useless
2. Penghilangan Produksi Unit
3. Penghilangan Produksi Empty (ε)

1. Penghilangan Produksi Useless

  • 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 awalsehingga produksi itu redundan(berlebih).
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 Persentasi "Penyederhaan Tata Bahasa Bebas Konteks" Dosen pengampu Teori Bahasa Automata: Garno, M.Kom. Fakultas Ilmu Komputer Universitas Singaperbangsa Karawang
https://herilovemetallica.blogspot.com/2009/10/penyederhanaan-tata-bahasa-dalam-teori.html
https://slideplayer.info/slide/3649861/

Komentar

Posting Komentar