Teknik-teknik Penyederhanaan Produksi Empty, Unit, dan Useless

 Tugas Materi 5 

Teknik-teknik Penyederhanaan Produksi Empty, Unit, dan Useless

1. Produksi Empty

Produksi ε adalah produksi dalam bentuk a → ε atau bisa dianggap sebagai produksi kosong (empty). Penghilangan produksi e

dilakukan dengan melakukan penggantian produksi yang memuat variabel yang bisa menuju produksi e, atau biasa disebut nullable.

Prinsip penggantiannya bisa dilihat kasus berikut:

S → bcAd

A → ε

A nullable serta A → ε satu-satunya produksi dari A, maka variabel A bisa

Contoh :

terdapat tata bahasa bebas konteks sebagai berikut :

S -> aB | Cd

A -> d

C -> ε

Variable 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.

Hasil penyederhanaannya adalah :

S -> aB | d

A -> d

2. Produksi Unit

Produksi Unit adalah produksi dimana ruas kiri dan kanan aturan produksi hanya berupa satu simbol variabel. Contoh : A -> B, C -> D

keberadaan produksi unit ini membuat tata bahasa memiliki kerumitan yang tak perlu. Penyederhanaan dilakukan dengan melakukan penggantian aturan produksi unit.

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 dituliskan 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. Produksi Useless

Produksi Useless didefinisikan sebagai berikut :

1. Produksi yang memuat simbol variable yang tidak memiliki penurunan yang akan menghasilkan terminal-terminal seluruhnya

2. Produksi yang tidak akanpernah dicapai dengan penurunan apapun dari simbol awal, sehingga produk itu redudan (berlebih)

Contoh :

Terdapat aturan produksi sebagai berikut :

S -> aBD

B -> cD | Ab

D -> ef

A -> Ed

F -> dc

Analisa :

1) Pada aturan produksi A -> Ed, E tidak memiliki penurunan. sehingga dapat dihilangkan

2) Aturan produksi F -> dc, redudan. sehingga aturan produksi tersebut dapat dihilangkan

Sisa aturan produksi yang telah disederhanakan adalah sebagai berikut :

S -> aBD

B -> cD | Ab

D -> ef

Analisa kembali :

aturan produksi B -> Ab, A tidak memiliki penurunan. sehingga didapat penyederhanaan lagi menjadi

S -> aBD

B-> cD

D -> ef

Kesimpulannya adalah bahwa produk useless yang dihilangkan adalah :

A-> Ed

F -> dc

B-> Ab

Untuk Melihat Video 

Menjelaskan Teknik-teknik Menyederhanakan Produksi Empty, Unit dan Useless
Ada Dibawah Sini..