PENYEDERHAAN TATA BAHASA BEBAS KONTEKS

Teori Bahasa dan Automata

Penyederhanaan Tata Bahasa Bebas Konteks

Tujuan dari penyederhaan ini adalah melakukan pembatasan sehingga tidak menghasilkan pohon penurunan yang memiliki kerumitan yang tidak perlu atau memotong aturan produksi yang tidak diperlukan. 

Dalam tata bahasa bebas konteks ini dapat dilakukan dengan 3 cara, yaitu :

1. Penghilangan produksi useless
2. Penghilangan produksi unit
3. Penghilangan produksi empty (𝜀)

Penghilangan Produksi Useless 

Penghilangan produksi useless, yaitu :

• Produksi yang memuat simbol variabel yang tidak memiliki penurunan yang akan menghasilkan simbol terminal.
• Produksi yang tidak akan pernah dicapai dengan penurunan apapun dari symbol awal sehingga produksi itu redundan (berlebih).

Contoh 1 (useless) :

Terdapat aturan produksi sebagai berikut 

S → aB | C

B → e | Ab

C → bCb | adF | ab

F → cFB 

Maka produksi yang useless beserta penjelasannya : 

1. B →  Ab (A tidak mempunyai penurunan. Maka dapat di hapus)
2. F →  cFB (F tidak memiliki penurunan yang menuju ke terminal dan F adalah dirinya sendiri. Maka dapat dihapuskan)
3. C →  adF (konsekuensi pada no(2) aturan produksi C →  adF tidak memiliki penurunan. Maka dapat dihapuskan)

Sehingga hasil penyederhanaan : 

Contoh 2 (useless) :

Terdapat aturan produksi sebagai berikut 

S → Aa | B

A → ab | D

B → b | E

C → bb

E → aEa 

Maka produksi yang useless beserta penjelasannya : 

1. A → D (D tidak memiliki penurunan. Maka dapat dihapuskan)
2. C → bb (aturan produksi ini merupakan redundan karena penurunan dari simbol S dengan jalan manapun tidak akan pernah mencapai C. Maka dapat dihapuskan)
3. E → aEa (E tidak memiliki penurunan yang menuju ke terminal dan E adalah dirinya sendiri. Maka dapat dihapuskan)
4. B → E (konsekuensi pada no(3) aturan produksi B →  E tidak memiliki penurunan. Maka dapat dihapuskan)

Sehingga hasil penyederhaan useless : 

Penghilangan Produksi Unit 

Penghilangan produksi unit, yaitu :  

• Produksi unit merupakan suatu produksi dimana ruas kiri dan ruas kanan aturan produksi hanya berupa satu symbol variabel, misalkan A → D.
• Penyederhanaan dilakukan dengan melakukan penggantian aturan produksi unit.
• Penggantian produksi unit dapat dilakukan dengan berurutan mulai dari aturan produksi yang paling dekat menuju ke penurunan terminal.

Contoh 1 (unit) :

Terdapat aturan produksi sebagai berikut 

S → Aa | B

B → A | bb

A → a | bc | B 

Penggantian yang dilakukan ("⇒" dibaca "menjadi") yaitu : 

B → A | bb       ⇒ B → a | bc | bb

A → a | bc | B   ⇒ A → a | bc | bb

S → Aa | B       ⇒ S → Aa | a | bc | bb

Sehingga hasil penyederhaan unit :

Contoh 2 (unit) : 

Terdapat aturan produksi sebagai berikut 

S → A | Aa

A → B

B → C | b

C → D | ab

D → b  

Penggantian yang dilakukan ("⇒" dibaca "menjadi") yaitu : 

C → D | ab    ⇒ C → b | ab 

B → C | b      ⇒ B → ab | b 

A → B           ⇒ A → ab | b 

S → A | Aa    ⇒ S → ab | b | Aa 

Sehingga hasil penyederhanaan unit : 

Penghilangan Produksi Empty (𝜀)

Penghilangan produksi empty (𝜀) yaitu :

• Produksi ε merupakan produksi dalam bentuk α → 𝜀 atau bisa dianggap sebagai produksi kosong
• Penghilangan produksi ε dapat dilakukan dengan penggantian produksi yang memuat variabel yang bisa menuju produksi ε atau bisa disebut nullable

Prinsip penggantiannya bisa dilihat seperti ini :

S → Abc

A → 𝜀

A nullable, serta A → ε merupakan satu-satunya produksi dari A, maka variabel A dapat dihapuskan. Hasil penyederhanaannya menjadi :

S → bc

Tetapi bila kasusnya :

S → Abc

A → cd | 𝜀

Dimana, A nullable tetapi A → ε bukan satu-satunya produksi dari A, maka hasil penyederhanaan nya menjadi :

S → Abc | bc

A → cd

Contoh 1 (empty):
S → AB
A → abB ⏐ aCa ⏐ 𝜀
B → bA ⏐ BB ⏐ 𝜀
C → 𝜀

Variabel yang nullable adalah C, B, A.

Karena C → 𝜀 merupakan satu-satunya produksi dari C, maka dapat langsung kita hapuskan :

A → aCa ⇒ A → aa 
C → 𝜀 kita hapus 

Selanjutnya, B → 𝜀 dan A → 𝜀 karena bukan satu-satunya produksi, maka dapat kita ganti : 
*karena variabel S → AB yang merupakan nullable, maka S bisa saja memproduksi empty, tetapi tidak akan dihapus karena merupakan produksi awal.
S → AB            ⇒ S → AB ⏐ A ⏐ B ⏐ 𝜀
A → abB           ⇒ A → abB ⏐ ab
B → bA ⏐ BB   ⇒ B → bA ⏐ b ⏐ BB 
B → 𝜀, A → 𝜀 kita hapus

Sehingga hasil penyederhanaan empty : 

Contoh 2 (empty) : 

S → aBCD | bb | A | 𝜀

A → CDa | ef

B → b | Af | 𝜀

C → BbC | ea

D → 𝜀 

Variabel yang nullable adalah S, B, D.
Karena D → ε merupakan satu-satunya produksi dari D, maka dapat langsung kita hapuskan :
S → aBCD  ⇒ S → aBC | bb | A | 𝜀
A → CDa    ⇒ A → Ca | ef
D → 𝜀, dihapuskan.

Selanjutnya, B → 𝜀 karena bukan satu-satunya produksi, maka dapat kita ganti : 
*karena variabel S → aBC, C → BbC yang merupakan nullable, maka bisa saja memproduksi empty, tetapi tidak akan dihapus karena merupakan produksi awal. 
S → aBC  ⇒ S → aBC | bb | A | aC | 𝜀
C → BbC ⇒ C → BbC | ae | bC 
B → 𝜀, kita hapus 

Karena S nya tidak ada di ruas kanan jadi dapat kita hapuskan langsung. 
Sehingga hasil penyederhanaannya empty : 

Alur Penyederhanaan Tata Bahasa Bebas Konteks pada Latihan Kompleks
Penyederhanaan ini dilakukan dengan menyederhanakan produksi useless, unit, dan empty secara bersamaan atau sekaligus, yaitu dengan alur sebagai berikut :

Contoh Latihan Kompleks 
Terdapat aturan produksi sebagai berikut : 
S  → BACa
B → AC
A → dC ⏐ 𝜀
C → D ⏐ 𝜀
D → d

Langkah 1, Hilangkan produksi empty
A dan C Nullable, tetapi A → 𝜀, C → 𝜀 bukan satu-satunya produksi yang menurunkan empty, maka dapat dilakukan penggantian :
S → BACa    ⇒ S → BACa ⏐ BCa ⏐ BAa ⏐Ba
B → AC        ⇒ B → AC ⏐ A ⏐ C⏐ 𝜀
A → dC         ⇒ A → dC ⏐ d
A → 𝜀 dan C → 𝜀, dihapuskan.
Karena variabel B menurunkan variabel yang akan menuju ke produksi empty, maka variabel B nullable. Kita lakukan Penggantian lagi :
S  → BACa ⏐ BCa ⏐ BAa ⏐ Ba ⟹ S → BACa ⏐ BCa ⏐ BAa ⏐ Ba ⏐ ACa ⏐ Ca ⏐ Aa ⏐ a
B → 𝜀 dihapuskan.
Maka aturan produksi setelah penghilangan empty :
S → BACa ⏐ BCa ⏐ BAa ⏐ Ba ⏐ ACa ⏐ Ca ⏐ Aa ⏐ a
B →  AC ⏐ A ⏐ C
A → dC ⏐ d
C → D
D → d

Langkah 2, Hilangkan produksi unit dari hasil penghilangan empty diatas
Penggantian produksi unit :
C → D   ⇒ C → d
B → C   ⇒ B → d
B → A   ⇒ B → dC ⏐ d
Maka aturan produksi setelah penghilangan produksi unit :
S → BACa ⏐ BCa ⏐ BAa ⏐ Ba ⏐ ACa ⏐ Ca ⏐ Aa ⏐ a
B → AC ⏐ dC ⏐  d
A → dC ⏐ d
C → d
D → d

Langkah 3, Hilangkan produksi useless dari hasil penghilangan produksi unit diatas
D → d merupakan redundan, karena penurunan dari produksi S tidak akan pernah menuju ke variabel D. Maka D → d, dapat dihapuskan.
Hasil Penyederhanaan latihan kompleks adalah :

Berikut adalah video penjelasan mengenai Penyederhaan Tata Bahasa Bebas Konteks ☺️

Semoga artikel dan video ini dapat membantu dalam mengerjakan soal-soal tentang Penyerderhanaan Tata Bahasa Bebas Konteks. Mohon maaf bila ada kesalahan dalam penulisan dan ucapan. Karena kesalahan hanya milik manusia dan kebenaran hanya milik Allah swt. Terima kasih☺️

Daftar Pustaka  : 

Materi 5 Tata Bahasa Bebas Konteks (Penyederhanaan) Dosen  pengampu Teori Bahasa dan Automata : Garno, M.Kom Fakultas Ilmu Komputer Universitas Singaperbangsa Karawang. 

Repository.unikom.ac.id (2012/2013). Penyederhanaan Tata Bahasa Bebas Konteks diakses melalui https://repository.unikom.ac.id/45133/1/Penyederhanaan%20Tata%20Bahasa%20Bebas%20Konteks.pdf