Penyederhanaan Tata Bahasa Bebas Konteks

Tujuan Penyederhanaan

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

Langkah-langkah penyederhanaan dari tatabahasa bebas konteks ini adalah dengan cara :

1. Menghilangkan produksi yang useless (tidak berguna)
2. menghilangkan produksi unit
3. menghilangkan produksi ε 

Apa yang dumaksud dengan produksi useless, produksi unit dan produksi ε ? dan bagaimana cara menghilangkannya ? mari kita lihat pembahasannya berikut ini.

• Penghilangan Produksi Useless 

Produksi yang memuat simbol variable yang tidak memiliki penurunan yang akan menghasilkan terminal-terminal seluruhnya (menuju terminal), produksi ini tidak berguna karena bila diturunkan tidak akan pernah selesai (masih ada simbol variable tersisa).  Produksi yang tidak akan pernah dicapai dengan penurunan apapun dari simbol awal, sehingga produksi itu redundan (berlebih).

1.      Hilangkan aturan yang tidak menuju terminal.

2.      Hapus anggota S yang mengandung simbol ke terminal yang tidak berguna.

3.      Hilangkan redundan (anggota yang tidak ada di S dan sebaliknya).

Contoh :

1.      S → aB | C

B → e |Ab

C → bCb | adF | ab

F → cFB

Jawab

•      Langkah Pertama

Hilangkan F → cFB karena tidak menuju ke terminal.

Sehingga menjadi :

S → aB | C

B → e |Ab

C → bCb | ab (adF dihilangkan karena F sudah tidak memiliki penurunan).

• Langkah Kedua

Hilangkan B → Ab karena A tidak memiliki penurunan.

Sehingga menjadi :

S → aB | C

B → e

C → bCb | adF | ab

F → cFB

➥ Maka hasil akhir penyederhanaan produksi useless dari soal diatas adalah :

S → aB | C

B → e

C → bCb | adF | ab

F → cFB

2.      S → Aa | B

A → ab | D

B → b | E

C → bb

E → aEa

Jawab :

• Langkah Pertama

Hilangkan E → aEa karena E tidak menuju ke terminal.

Sehingga menjadi :

S → Aa | B

A → ab | D

B → b (E dihilangkan karena E sudah tidak memiliki penurunan)

C → bb

Langkah Kedua

Hilangkan C → bb karena C redundan.

Sehingga menjadi :

S → Aa | B

A → ab | D

B → b

•   Langkah Ketiga

Hilangkan A → D Karena D tidak memiliki penurunan.

S → Aa | B

A → ab

B → b

➥  Maka hasil akhir penyederhanaan produksi useless dari soal diatas adalah :

S → Aa | B

A → ab

B → b

• Penghilangan Produksi Unit

Produksi unit adalah produksi yang ruas kiri dan kanan aturan produksinya hanya berupa satu simbol variable misalkan: A → B. ( a = 1 N/V dan b = 1 N/V ) Dengan adanya bentuk produksi unit ini membuat tata bahasa memiliki kerumitan yang tidak perlu atau menambah panjang penurunan. Penyederhanaan ini dilakukan dengan melakukan penggantian aturan produksi unit.


Langkah Penyederhanaannya :
1. Jabarkan masing-masing himpunan.
2. Sederhanakan ruas kiri dan ruas kanan yang hanya berupa variabel simbol sama.
3. Hapus simbol variabel yang tidak berguna / tidak mempunyai turunan.

Contoh :

1.      S → Aa | B

B → A | bb

A → a | bc | B

Jawab :

•   Langkah Pertama

Ubah A → B menjadi A → A | bb (namun A tidak usah di masukan karena akan useless).

Sehingga menjadi :

S → Aa | B

B → A | bb

A → a | bc | bb

•   Langkah Kedua

Ubah B → A menjadi B → a | bc

Sehingga menjadi :

S → Aa | B

B → a | bc | bb

A → a | bc | bb

•   Langkah Ketiga

Ubah S → B menjadi S → a | bc | bb

Sehingga menjadi :

S → Aa | a | bc | bb

B → a | bc | bb

A → a | bc | bb

➥  Maka hasil akhir penyederhanaan unit dari soal diatas adalah :

S → Aa | a | bc | bb

B → a | bc | bb

A → a | bc | bb

2.      S → A | Aa

A → B

B → C | b

C → D | ab

D → b

Jawab :

•   Langkah Pertama

Ubah C → D menjadi C → b

Sehingga menjadi :

S → A | Aa

A → B

B → C | b

C → b | ab

D → b

•   Langkah Kedua

Ubah B → C menjadi B → b | ab

Sehingga menjadi :

S → A | Aa

A → B

B → b | ab (bukan B → b | ab | b karena b sudah ada, jadi hanya ditulis satu kali)

C → b | ab

D → b

•   Langkah Ketiga

Ubah A → B menjadi A → b | ab

Sehingga menjadi :

S → A | Aa

A → b | ab

B → b | ab

C → b | ab

D → b

•   Langkah Keempat

Ubah S → A menjadi S → b | ab

S →  b | ab | Aa

A → b | ab

B → b | ab

C → b | ab

D → b

➥  Maka hasil akhir penyederhanaan unit dari soal diatas adalah :

S →  b | ab | Aa

A → b | ab

B → b | ab

C → b | ab

D → b

• Penghilangan produksi e (empty)

Produksi e (Empty) adalah produksi dalam bentuk a → e atau bisa dianggap sebagai produksi kosong. Penghilangan produksi e dilakukan dengan melakukan penggantian produksi yang memuat variable yang menuju ke produksi e, atau biasa disebut nullable.


Langkah Penyederhanaannya :
1. Hilangkan simbol yang terdapat e (empty) dalam himpunan produksi.
2. Simbol variabel tidak di hapus jika terdapat cabang teriminal/variabel yang saling berhubungan.
3. Buat himpunan dengan simbol yang dihilangkan dan yang tidak.

Contoh :

1.      S → AB

A → abB | aCa | ε

B → bA | BB | ε

C → ε

Jawab :

• Langkah Pertama

Hilangkan produksi ε pada C → ε

Sehingga menjadi :

S → AB

A → abB | aa | ε

B → bA | BB | ε

•   Langkah Kedua

Hilangkan produksi ε pada B → bA | BB | ε

Sebenarnya disini bebas ingin menghilangkan ε pada A → abB | aa | ε atau B → bA | BB | ε. Tetapi saya lebih memilih menghilangkan pada B → bA | BB | ε Terlebih dahulu.

Sehingga menjadi :

S → AB | A

A → abB | aa | ab | ε

B → bA | BB | B

•   Langkah Ketiga

Hilangkan produksi ε pada A → abB | aa | ε.

Sehingga menjadi :

S → AB | A | B

A → abB | aa | ab

B → bA | BB | B | b

➥  Maka hasil akhir penyederhanaan empty dari soal diatas adalah :

S → AB | A | B

A → abB | aa | ab

B → bA | BB | B | b

2.      S → aBCD | bb | A | ε

A → CDa | ef

B → b | Af | ε

C → BbC | ea

D → ε

Jawab :

•   Langkah Pertama

Hilangkan produksi ε pada D → ε

Sehingga menjadi :

S → aBC | bb | A | ε

A → Ca | ef

B → b | Af | ε

C → BbC | ea

•   Langkah Kedua

Hilangkan produksi ε pada B → b | Af | ε

Sehingga menjadi :

S → aBC | bb | A | aC | ε

A → Ca | ef

B → b | Af

C → BbC | ea | bC

•   Langkah Ketiga

Hilangkan produksi ε pada S → aBC | bb | A | aC | ε

Sehingga menjadi :

S → aBC | bb | A | aC

A → Ca | ef

B → b | Af

C → BbC | ea | bC

➥  Maka aasil akhir penyederhanaan produksi empty dari soal diatas adalah :

S → aBC | bb | A | aC

A → Ca | ef

B → b | Af

C → BbC | ea | bC

• Penyederhanaan Produksi Kompleks

Penyederhanaan ini adalah gabungan dari penyederhanaan produksi useless, penyederhanaan produksi unit dan penyederhanaan produksi ε (empty).


Langkah penyederhanaan produksi kompleks :
1. Lakukan penyederhanaan produksi ε (empty) terlebih dahulu.
2. Kemudian, lakukan penyederhanaan produksi unit.
3. Terakhir, lakukan penyederhanaan useless.

Contoh :

1.      S → BACa

B → AC

A → dC | ε

C → D | ε

D → d

Jawab :

•  Langkah Pertama (Lakukan Penyederhanaan Produksi Empty)

Hilangkan produksi ε pada C → D | ε

Sehingga menjadi :

S → BACa  | BAa

B → AC | A

A → dC | d | ε

C → D

D → d

Hilangkan produksi ε pada A → dC | ε

Sehingga menjadi :

S → BACa  | BAa | BCa | Ba

B → AC | A | C | ε

A → dC | d

C → D

D → d

Hilangkan produksi ε pada B → AC | A | C | ε

Sehingga menjadi :

S → BACa  | BAa | BCa | Ba | ACa | Aa | Ca | a

B → AC | A | C

A → dC | d

C → D

D → d

•  Langkah Kedua (Lakukan Penyederhanaan Produksi Unit)

Ubah C → D menjadi C → d

Sehingga menjadi :

S → BACa  | BAa | BCa | Ba | ACa | Aa | Ca | a

B → AC | A | C

A → dC | d

C → d

D → d

Ubah B → A menjadi B → dC | d

Sehingga menjadi :

S → BACa  | BAa | BCa | Ba | ACa | Aa | Ca | a

B → AC | dC | d | C

A → dC | d

C → d

D → d

Ubah B → C menjadi B → d

Sehingga menjadi :

S → BACa  | BAa | BCa | Ba | ACa | Aa | Ca | a

B → AC  | dC | d

A → dC | d

C → d

D → d

§  Langkah Ketiga (Lakukan Penyederhaan Produksi Useless)

Hilangkan D → d karena redundan

Sehingga menjadi

S → BACa  | BAa | BCa | Ba | ACa | Aa | Ca | a

B → AC | dC | d

A → dC | d

C → d

§  Maka hasil akhir penyederhanaan kompleks dari soal diatas adalah :

S → BACa  | BAa | BCa | Ba | ACa | Aa | Ca | a

B → AC  | dC | d

A → dC | d

C → d

Berikut Pembahasan Mengenai Penyederhanaan Tata Bahasa Bebas Konteks 

Melalui  Video dengan beberapa soal yang ada di atas.

Semoga Video Tersebut bisa terlihat jelas dan mudah di mengerti

Terimakasih 😃😃