Penyederhanaan tata bahasa bebas konteks adalah dengan cara

Penyederhanaan tata bahasa bebas konteks bertujuan untuk melakukan sehingga tidak menghasilkan pohon penurunan yang memiliki kerumitan yang tidak perlu atau aturan produksi yang tidak berarti.
Suatu tata bahasa bebas konteks dapat melakukan penyederhanaan dengan melakukan cara :

1. Penghilangan produksi Useless
2. Penghilangan produksi Unit
3. Penghilangan produksi ε

Penghilangan Produksi Useless

Definisi produksi Useless adalah 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 variabel tersisa). Dan juga produksi Useless memiliki definisi lain yaitu produksi yang tidak akan pernah dicapai dengan penurunan apapun dari simbol awal, sehingga produksi itu redundan (berlebih).

Contoh :Diketahui tata bahasa bebas konteks sebagai berikut :S → Aa | BA → ab | DB → b | EC → bbE → aEaAnalisis :1. Aturan produksi A → D, variabel D tidak memiliki penurunan, sehingga bisa dihilangkan.2. Aturan produksi C → bb, jika dilakukan dengan penurunan dari simbol awal S, dengan jalan mana pun tidak akan pernah tercapai. Sehingga bisa dihilangkan.3. Simbol variabel E tidak memiliki aturan produksi yang menuju terminal, sehingga bisa dihilangkan.4. Konsekuensi no. 3, aturan produksi B → E, simbol variabel E tidak memiliki penurunan, sehingga bisa dihilangkan.Maka tata bahasa hasil penyederhanaannya menjadi :S → Aa | BA → ab

B → b

Penghilangan Produksi Unit

Produksi unit adalah produksi yang ruas kanan dan ruas kirinya memiliki aturan produksi hanya berupa satu simbol variabel. Penyederhanaan ini dilakukan dengan melakukan penggantian aturan produksi unit.Contoh :Diketahui tata bahasa bebas konteks sebagai berikut :S → SbS → CC → DC → efD → ddAnalisis :Lakukan penggantian berurutan mulai dari aturan produksi yang paling dekat menuju terminal-terminal.C → D menjadi C → ddS → C menjadi S → dd | efHasil penyederhanaan :S → Sb | dd | efC → dd | ef

D → dd

Penghilangan Produksi Empty (ε)

Penghilangan produksi empty adalah :
• Produksi ε (Empty) adalah produksi dalam bentuk α → ε atau bisa dianggap produksi kosong.
• Penghilangan produksi empty dilakukan dengan melakukan penggantian produksi yang memuat variabel yang menuju produksi ε, atau biasa disebut nullable.Contoh :Diketahui tata bahasa bebas konteks sebagai berikut :S → dA | BdA → bcA → εB → cAnalisis :1. A → ε dihapus karna menghasilkan ε2. S → dA berubah menjadi S → dA | dHasil penyederhanaan :S → dA | d | BdA → bc

B → c

Gabungan Useless, Unit dan Empty

Urutan penyederhanaan dari gabungan useless, unit, dan empty, yaitu :

Contoh :
Hilangkan produksi uselesss, unit dan empty dari tata bahasa bebas konteks berikut :S → a | aA | B | CA → aB | εB → Aa | aC → cCDD → ddd

Tahap 1 : Penghilangan produksi empty

Hasil penyederhanaan/penghilangan produksi empty :

Hasil penyederhanaan/penghilangan produksi unit dan empty :

Tahap 3 : Penghilangan produksi useless

Hasil penyederhanaan/penghilangan produksi empty, unit dan useless :

A → aB | a

Itulah penjelasan tentang penyederhanaan tata bahasa bebas kompleks. Berikut adalah video penjelasan latihan penyederhanaan tata bahasa bebas kompleks.

Referensi :
https://repository.unikom.ac.id/45133/1/Penyederhanaan%20Tata%20Bahasa%20Bebas%20Konteks.pdf
https://www.scribd.com/doc/293082099/8-Penyederhanaan-Tata-Bahasa-Bebas-Konteks
https://slideplayer.info/slide/12678996/

1 PENYEDERHANAAN TATA BAHASA BEBAS KONTEKS
*YANI*

2 PENYEDERHANAAN TATA BAHASA BEBAS KONTEKS
Penyederhanaan tata bahasa bebas konteks bertujuan untuk melakukan pembatasan sehingga tidak menghasilkan pohon penurunan yang memiliki kerumitan yang tak perlu atau aturan produksi yang tidak berarti. Misalkan terdapat tata bahasa bebas konteks : S → AB | a A → a Kelemahan tata bahasa bebas konteks di atas, aturan produksi S → AB tidak berarti karena B tidak memiliki penurunan.

3 PENYEDERHANAAN TATA BAHASA BEBAS KONTEKS
Untuk tata bahasa bebas konteks berikut. S → A A → B B → C C → D D → a | A Memiliki kelemahan terlalu panjang jalannya padahal berujung pada S → a, produksi D → A juga memiliki kerumitan.

4 LANGKAH – LANGKAH PENYEDERHANAAN
Suatu tata bahasa bebas konteks dapat disederhanakan dengan melakukan cara berikut ini. 1. Penghilangan produksi useless (tidak berguna) 2. Penghilangan produksi unit. 3. Penghilangan produksi є

5 Penghilangan Produksi Useless
Penghilangan produksi useless dilakukan dengan cara sebagai berikut. 1. Menghilangkan produksi yang memuat simbol variabel yang tidak memiliki penurunan yang akan menghasilkan simbol terminal. 2. Produksi yang tidak akan pernah dicapai dengan penurunan apapun dari simbol awal sehingga produksi itu redundan (berlebih).

6 Penghilangan Produksi Useless
Contoh, terdapat tata bahasa bebas konteks : S → aSa | Abd | Bde A → Ada B → BBB | a Kita bisa melihat bahwa : 1. Simbol variabel A tidak memiliki penurunan yang menuju terminal, sehingga bisa dihilangkan. 2. Karena simbol A telah dihilangkan, maka dengan sendirinya S → Abd juga dihilangkan.

7 Penghilangan Produksi Useless
Maka dari tata bahasa bebas konteks di atas, produksi yang useless : A → Ada S → Abd Maka tata bahasa bebas konteks setelah disederhanakan menjadi : S → aSa | Bde B → BBB | a

8 Penghilangan Produksi Useless
Contoh lain, terdapat tata bahasa bebas konteks sebagai berikut. S → Aa | B A → ab | D B → b | E C → bb E → aEa

9 Penghilangan Produksi Useless
Kita bisa melihat bahwa : 1. Aturan produksi A → D, simbol variabel D tidak memiliki penurunan, sehingga bisa dihilangkan 2. Aturan produksi C → bb, bila kita coba melakukan penurunan dari simbol awal S, dengan jalan manapun tidak akan pernah mencapai C, sehingga bisa dihilangkan. 3. Simbol variabel E tidak memiliki aturan produksi yang menuju terminal, sehingga bisa dihilangkan. 4. Konsekuensi dari aturan no. 3 maka aturan produksi B → E, juga mesti dihilangkan.

10 Penghilangan Produksi Useless
Maka dari tata bahasa bebas konteks tersebut produksi yang useless adalah sebagai berikut. A → D C → bb E → aEa B → E

11 Penghilangan Produksi Useless
Maka tata bahasa bebas konteks setelah disederhanakan menjadi : S → Aa | B A → ab B → b

12 Penghilangan Produksi Useless
Contoh lain, terdapat tata bahasa bebas konteks berikut. S → aAb | cEB A → dBE | eeC B → ff C → ae D → h

13 Penghilangan Produksi Useless
Kita bisa melihat bahwa : 1. S → cEB, E tidak memiliki penurunan, sehingga bisa dihilangkan. 2. A → dBE, E tidak memiliki penurunan sehingga bisa dihilangkan. 3. D → h, tidak dapat dicapai melalui penurunan manapun sehingga redundan. 4. B → ff, karena S → cEB dan A → dBE sudah dihilangkan, maka tidak akan dapat dicapai melalui penurunan manapun sehingga bisa dihilangkan.

14 Penghilangan Produksi Useless
Maka aturan produksi yang useless adalah sebagai berikut. S → cEB A → dBE D → h B → ff Sehingga tata bahasa bebas konteks hasil penyederhanaan adalah sebagai berikut. S → aAb A → eeC C → ae

15 Penghilangan Produksi Useless
Contoh lain, terdapat tata bahasa bebas konteks berikut. S → aB A → bcD | dAC B → e | Ab C → bCb | adF | ab F → cFB

16 Penghilangan Produksi Useless
Kita bisa melihat bahwa : 1. Aturan produksi F → cFB tidak memiliki penurunan yang menuju ke simbol terminal sehingga bisa dihilangkan. 2. A → bcD, variabel D tidak memiliki penurunan, sehingga bisa dihilangkan 3. A → dAC, tidak memiliki penurunan yang menghasilkan simbol terminal sehingga bisa dihilangkan. 4. Konsekuensi dari no. 2 dan no.3, maka B → Ab, juga dihilangkan. 5. C → adF juga dihilangkan, karena F telah dihilangkan.

17 Penghilangan Produksi Useless
Maka aturan produksi setelah disederhanakan menjadi : S → aB B → e C → bCb | ab

18 Penghilangan Produksi Useless
Contoh lain, terdapat tata bahasa bebas konteks sebagai berikut. S → aBD B → cD | Ab D → ef A → Ed F → dc Kita bisa melihat bahwa : 1. Aturan produksi A → Ed, E tidak memiliki penurunan sehingga bisa dihilangkan. 2. Sebagai konsekuensi dari no.1 maka B → Ab juga dihilangkan

19 Penghilangan Produksi Useless
3. F → dc, tidak dapat dicapai dari penurunan apapun sehingga bisa dihilangkan. Maka tata bahasa bebas konteks setelah disederhanakan menjadi : S → aBD B → cD D → ef

20 LATIHAN SOAL Soal : 1. Hilangkanlah semua aturan produksi yang useless dari tata bahasa bebas konteks berikut S → AB | CA B → BC | AB A → a C → aB | b 2. Hilangkan semua aturan produksi yang useless dari tata bahasa bebas konteks berikut. S → aS | A | C B → aa C → aCb

21 LATIHAN SOAL 3. Hilangkan semua aturan produksi yang useless dari tata bahasa bebas konteks berikut. S → A A → aA | є B → bA

22 Penghilangan Produksi Unit
Produksi unit adalah produksi di mana ruas kiri dan kanan aturan produksi hanya berupa satu simbol variabel, misalkan : A → B, C → D. Keberadaan produksi unit membuat tata bahasa memiliki kerumitan yang tak perlu atau menambah panjang penurunan. Penyederhanaan ini dilakukan dengan melakukan penggantian aturan produksi unit.

23 Penghilangan Produksi Unit
Contoh tata bahasa bebas konteks : S → Sb S → C C → D C → ef D → dd

24 LANGKAH - LANGKAH Langkah-langkahnya adalah sebagai berikut :
1. Kita lihat untuk S → C C → D lalu D → dd sehingga C → dd C → ef Maka S → C dapat diubah menjadi S → dd | ef 2. Kita lihat untuk C → D Maka C → D dapat diubah menjadi C → dd

25 Sehingga tata bahasa bebas konteks setelah penyederhanaan adalah sebagai berikut.
S → Sb S → dd | ef C → dd C → ef D → dd

26 CONTOH Contoh lain, terdapat tata bahasa bebas konteks : S → A S → Aa
B → C B → b C → D C → ab D → b

27 CONTOH Penggantian yang dilakukan : 1. S → A
Untuk S → A maka setelah ditelusuri menghasilkan S → b | ab 2. A → B Untuk A → B maka setelah ditelusuri menghasilkan A → b | ab 3. B → C Untuk B → C maka setelah ditelusuri menghasilkan B → b | ab Untuk B → b sudah ada, maka cukup ditulis B → ab 4. C → D Untuk C → D maka setelah ditelusuri menghasilkan C → b | ab Untuk C → ab sudah ada, maka cukup ditulis C → b

28 CONTOH Sehingga tata bahasa bebas konteks setelah disederhanakan menjadi : S → ab | b S → Aa A → ab | b B → ab B → b C → b C → ab D → b

29 CONTOH Contoh lain, terdapat tata bahasa bebas konteks : S → Cba | D
A → bbC B → Sc | ddd C → eA | f | C D → E | SABC E → gh

30 CONTOH Penggantian yang dilakukan : 1. D → E menjadi D → gh
2. C → C, kita hapus 3. S → D menjadi S → gh | SABC Sehingga tata bahasa bebas konteks setelah penyederhanaan menjadi : S → Cba | gh | SABC A → bbC B → Sc | ddd C → eA | f D → gh | SABC E → gh

31 LATIHAN SOAL Soal : 1. Hilangkanlah semua aturan produksi unit dari tata bahasa bebas konteks berikut. S → Aa | B B → A | bb A → a | bc | B

32 LATIHAN SOAL 2. Hilangkan semua aturan produksi unit dari tata bahasa bebas konteks berikut. S → AbaC | BaC | AaC | Aba | aC | Aa | Ba | a A → B | C | BC B → b C → D D → d

33 Penghilangan Produksi є
Produksi є adalah produksi dalam bentuk : α → є atau bisa dianggap sebagai produksi kosong (empty). Penghilangan produksi є dilakukan dengan melakukan penggantian produksi yang memuat variabel yang bisa menuju ke produksi є, atau biasa disebut nullable.

34 Penghilangan Produksi є
Prinsip penggantiannya bisa dilihat pada kasus berikut ini. S → bcAd A → є Pada kasus diatas A nullable, serta A → є satu-satunya produksi dari A, maka variabel A bisa ditiadakan, hasil penyederhanaan tata bahasa bebas konteks menjadi : S → bcd

35 Penghilangan Produksi є
Tetapi bila kasusnya : S → bcAd A → bd | є Pada kasus di atas A nullable, tetapi A → є bukan satu-satunya produksi dari A, maka hasil penyederhanaan : S → bcAd | bcd A → bd

36 CONTOH Contoh, terdapat tata bahasa bebas konteks : S → Ab | Cd A → d
Variabel yang nullable adalah variabel C. Karena penurunan C → є merupakan penurunan satu-satunya dari C, maka kita ganti S → Cd menjadi S → d. Kemudian produksi C → є kita hapus. Tata bahasa bebas konteks setelah penyederhanaan : S → Ab | d

37 CONTOH Contoh lain, terdapat tata bahasa bebas konteks : S → dA | Bd
A → bc A → є B → c Variabel yang nullable adalah variabel A. A → є bukan penurunan satu-satunya dari A (terdapat A → bc), maka kita ganti S → dA menjadi S → dA | d. A → є kita hapus. Setelah penyederhanaan : S → dA | d | Bd

38 CONTOH Contoh lain, terdapat tata bahasa bebas konteks : S → AaCD
A → CD | AB B → b | є C → d | є D → є Variabel yang nullable adalah variabel B, C, D. Kemudian kita lihat A → CD, maka variabel A juga nullable, karena D hanya memiliki penurunan D → є, maka kita sederhanakan dulu : • S → AaCD menjadi S → AaC • A → CD menjadi A → C • D → є kita hapus

39 Selanjutnya kita lihat variabel B dan C memiliki penurunan є, meskipun bukan satu satunya penurunan, maka kita lakukan penggantian : A → AB menjadi A → AB | A | B S → AaC menjadi S → AaC | aC | Aa | a B → є dan C → є kita hapus Setelah penyederhanaan : S → AaC | aC | Aa | a A → C | AB | A | B B → b C → d

40 CONTOH Contoh lain, terdapat tata bahasa bebas konteks : S → AB
A → abB | aCa | є B → bA | BB | є C → є Variabel yang nullable adalah A, B, dan C. Dari S → AB, maka S juga nullable. Kita lakukan penggantian : S → AB menjadi S → AB | A | B A → abB menjadi A → abB | ab A → aCa menjadi A → aa B → bA menjadi B → bA | b B → BB menjadi B → BB | B C → є, B → є, dan A → є kita hapus.

41 CONTOH Hasil akhir penyederhanaan menjadi : S → AB | A | B
A → abB | ab | aa B → bA | b | BB | B

42 CONTOH Contoh lain, terdapat tata bahasa bebas konteks : S → aAb
A → aAb | є Hasil akhir penyederhanaan menjadi : S → aAb | ab A → aAb | ab

43 CONTOH Contoh lain, terdapat tata bahasa bebas konteks : S → ABaC
A → BC B → b | є C → D | є D → d Hasil penyederhanaan : S → ABaC | AaC | Aba | BaC | aC | Aa | Ba | a A → BC | B | C B → b C → D

44 SOAL 1. Hilangkanlah semua produksi є dari tata bahasa bebas konteks berikut. S → ABaC A → Bd B → b | є C → D | є D → BCa 2. Hilangkanlah semua produksi є dari tata bahasa bebas konteks berikut. S → AaB | aaB A → є B → bbA | є

45 SOAL 3. Hilangkanlah semua produksi є dari tata bahasa bebas konteks berikut. S → aSb | SS | є 4. Hilangkanlah semua produksi dari tata bahasa bebas konteks berikut. S → AB A → aA | abB | aCa B → bA | BB | є C → є D → dB | BCB

46 SOAL 5. Lakukan penghilangan produksi unit, useless, dan є dari tata bahasa bebas konteks berikut. S → a | aA | B | C A → aB | є B → Aa C → cCD D → ddd 6. Lakukan penghilangan produksi unit, useless, dan є dari tata bahasa bebas konteks S → aB | aaB A → є B → bA B → є

47 SOAL 7. Hilangkan semua aturan produksi useless dan unit dari tata bahasa bebas konteks berikut. S → AaC | aC | Aa | a A → C | AB | A | B B → b C → d