Teknik-Teknik Penyederhanaan Produksi Empty,Unit dan Useless

PENYEDERHANAAN TATA BAHASA BEBAS KONTEKS

Sebuah bahasa formal adalah abstraksi terdiri dari himpunan simbol-simbol dan aturan-aturan yang mana simbol-simbol tersebut bisa dikombinasikan kedalam entitas yang disebut kalimat.

Bahasa adalah himpunan string-string dari simbol-simbol untuk suatu alphabet atau rangkaian simbol-simbol yang mempunyai makna.Bahasa Kosong adalah bahasa yang tidak terdiri dari string-string, dinotasikan dengan ->. Bahasa kosong berbeda dengan bahasa yang terdiri dari string kosong {ε}.

Melakukan pembatasan sehingga tidak menghasilkan pohon penurunan yang memiliki kerumitan yang tidak perlu atau aturan produksi yang tidak berarti. contoh Penyederhanaan tata bahasa dalam Teori bahasa dan Otomata,berikut adalah :

Tujuan Penyederhanaan

Melakukan pembatasan sehingga tidak menghasilkan pohon penurunan yang memiliki kerumitan yang tidak perlu atau aturan produksi yang tidak berarti.
Contoh 1 :
S -> AB | a
A -> a
• Aturan produksi S -> AB tidak berarti karena B tidak memiliki penurunan

Contoh 2 :

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 menyebabkan kerumitan.

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 ε

Penghilangan Produksi Useless

Di sini produksi useless didefinisikan sebagai :
• Produksi yang memuat symbol variabel yang tidak memiliki penurunan yang akan menghasilkan terminal-terminal seluruhnya.
• Produksi yang tidak akan pernah dicapai dengan penurunan apapun dari simbol awal, sehingga produksi itu redundan ( berlebih ).

Contoh 1 :

S -> AB | C

B -> c | Ab

C -> bCb | adF | ab

F -> cFB

Dapat disimpulkan :

1. Aturan Produksi B -> Ab ( A tidak memiliki penurunan)

2. Aturan Produksi F -> cFB (F tidak memiliki penurunan yang menuju simbol terminal)

3. Aturan Produksi C -> adF (F tidak memiliki penuruanan)

Maka produksi yang useless :

B -> Ab

F -> cFB

C -> adF

Maka tata Bahasa bebas konteks setelah disederhanakan menjadi:

S -> aB | C

B -> e

C -> bcb | ab

Contoh 2 :

S-> Aa | B

A->ab | D

B->b | E

C-> bb

E-> aEa

Dapat disimpulkan  :
1) Aturan produksi A -> D, simbol variabel D tidak memiliki penurunan.
2) Aturan produksi C -> bb, Penurunan dari simbol S, dengan jalan manapun tidak akan pernah mencapai C.
3) Aturan produksi E -> aEa, Simbol variabel E tidak memiliki aturan produksi yang menuju terminal.
4) Konsekuensi no (3) Aturan produksi B -> E, simbol variabel E tidak memiliki penurunan.

Maka produksi yang useless :

A -> D
C -> bb

E -> aEa

B -> E

Maka tata Bahasa bebas konteks setelah disederhanakan menjadi:

S -> Aa | B

A -> ab

B -> b

Penghilangan Produksi Unit

• Produksi dimana ruas kiri dan kanan aturan produksi hanya berupa satu simbol variabel,      misalkan: A -> B, C > D.
• Keberadaannya membuat tata bahasa memiliki kerumitan yang tak perlu.

• Penyederhanaan dilakukan dengan melakukan penggantian aturan produksi unit.

Contoh 1 :

S -> Aa | B

B -> A | bb

A -> a | bc | b

Langkah – Langkah penggantian yang dilakukan :

S -> Aa’

S -> B a  | bc  | bb

B -> A a | bc  | bb

B -> bb

A -> a

A -> bc

A -> B bb

Sehingga aturan produksi setelah penyederhanaan :

S -> Aa | a | bc | bb

B -> a | bc | bb

A -> a | bc | bb

Contoh 2 :

S -> A | aa

A -> B

B -> c | b

C -> D | ab

D -> b

Langkah – Langkah penggantian yang dilakukan :

C -> D | ab menjadi C -> b | ab

B -> c | b menjadi B -> b | ab , B -> ab | b

A -> B menjadi A -> ab | b

S -> A menjadi S -> ab | b | Aa

Sehingga aturan produksi setelah penyederhanaan :

S -> ab | b | Aa

A -> ab | b

B -> ab | b

C -> b | ab

D -> b

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 produksi ε, atau biasa disebut nullable.

Contoh 1 :

S -> AB

A -> bA | aca | ε

B -> bA | BB | ε

C -> ε

Variabel yang nullable adalah A, B, C. dari S -> AB maka S juga disebut nullable

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 -> ε maka dihafus

Hasil penyederhanaan menjadi :

S -> AB | A | B

A -> abB | ab | aa

B -> bA | b | BB | B

Contoh 2 :

S -> aBcD | bb | ε

A -> cDa | cf

B -> b | af | ε

C -> Bbc | ea

Variabel yang nullable adalah S, B, D.

S -> aBcD menjadi S -> aBc | ac

A -> cDa menjadi A -> Ca

C -> Bbc menjadi C -> Bbc | bc

S -> ε, B -> ε, dan D -> ε maka dihafus

Hasil penyederhanaan menjadi :

S -> aBc | ac | bb | A

A -> Ca | ef

B -> b | Af

C -> BbC | bc | εa

Latihan Kompleks

Lakukan Penyederhanaan pada Himpunan produksi dengan penghilangan Empty + Unit + Useless sekaligus

S -> Baca

B -> Ac

A -> dc | ε

C -> D  | ε

D -> d

Hasil Penyederhanaan Empty (ε)

Langkah 1, hilangkan ε dan C

S -> BACa | Baa

B -> AC | A

A -> dC | ε | d

C -> D

D -> d

Lankah 2, hilangkan ε pada A

S -> BACa  | Baa

B -> AC  | A

A -> dC  | ε | d

C -> D

D -> d

Langkah 3, hilangkan ε pada B

S -> BACa | Baa | Ba | Aca | Aa | Ca | a

B -> AC | A | C

A -> dC | d

C -> D

D -> d

-selesai- pada Langkah Penyederhanaan empty (ε)

Hasil Penyederhanaan Unit

C -> diubah menjadi C - d

B ->  diubah menjadi B – d

B -> diubah mejadi B – dC | d

Jadi

S -> BaCa  | Baa  | BCa  | Ba  | Aca  |  Aa  |  Ca  |  a

B -> AC  |  dC  |  d

A -> dC  |  d

C -> d

D -> d

-selesai  pada Penyederhanaan Unit

Karena syarat Useless tidak ada yang terpenuhi maka langkah penyederhanaan selesai.

Berikut ini video penjelasan dari Latihan soal diatas :