Penyederhaan Tata Bahasa Bebas Konteks


"Penyederhaan Tata Bahasa Bebas Konteks"

Sebuah Tata Bahasa Bebas Konteks dapat disederhanakan dengan melakukan :
  1. Penghilangan Produksi Useless
  2. Penghilangan Produksi Unit
  3. Penghilangan Produk Empty

Berikut adalah penjelasan dari setiap teknik penyederhanaan :
1. Penghilangan Produksi Useless
(a) Produksi Useless adalah produksi yang memuat simbol variabel yang tidak memiliki turunan ke terminal-terminal seluruhnya.
(b) Produksi yang tidak akan mencapai turunan apapun dari simbol awal sehingga produksi itu disebut redundan

Contoh :
S → Ab | Bcd
A → BB | Adc
B → Bca | b
C → b

Kesimpulan :
a. A → Adc tidak memiliki penurunan yang menuju terminal maka dinyatakan useless.
b. B → Bca tidak memiliki penurunan yang menuju terminal maka dinyatakan useless.
c. yang menyebabkan S → Bcd tidak memiliki penurunan.
d. C bersifat redundan

Hasil Penyederhanaan :
S → Ab
A → BB

2. Penghilangan Produksi Unit
(a)  Produksi unit adalah produksi yang dimana masing-masing ruas aturan produksi memiliki satu variabel saja
Contoh 1 : A → B, C → D

Contoh 2 :
S → Sb
S → C 
C → D
C → ef
D → dd  


Penggantian Berurutan :
C → D  = C → dd
S → C  = S → dd | ef

Maka, Aturan Produksi setelah Penyederhanaan :
S → Sb
S → dd | ef
C → dd
C → ef
D → dd

3. Penghilangan Produksi Empty
(a) Penghilangan produksi ε dilakukan dengan penggantian produksi yang memuat variabel yang bisa menuju produksi εε atau biasa disebut nullable.

Contoh 1 :
S → Bc | Ab
A → bc 
B → ε

Maka :
(a) Menghilangakan B → ε
Dengan cara menghilangkan B pada aturan Produksi S → Bc
S → c | Ab
A → bc 


Contoh 2 :
Bagaimana jika Empty bukan satu-satunya aturan produksi terminal?
S → bcAd
A → bd | ε

Maka :
(a) Menghilangakan A → ε
Dengan cara menambahkan aturan produksi S dengan menghilangkan A di bcAd
Maka terbentuklah Aturan Produksi S → bcd
S → bcAd | bcd
A → bd

Contoh Soal Kompleks : 
S → BACa
B → AC
A → dC | ε
C → D | ε
D → d

Langkah Pertama :
(Penghilangan Produksi Empty)
(a) Menghilangkan C → ε
Dengan cara menduplikasi BACa tetapi menghilangkan C terbentuklah aturan Produksi S → BAa.
Menduplikasi AC tetapi menghilangkan C terbentuklah aturan Produksi  S → A
S → BACa | BAa
B → AC | A
A → dC | d | ε
C → D
D → d

(b) Menghilangkan A → ε
Dengan cara menduplikasi B →  BACa dan B →  BAa namun menghilangkan A
Menduplikasi B → AC | A namun menghilangkan A
S → BACa | BAa | BAa | Ba 
B → AC | A | C | ε (nullable baru)
A → dC | d
C → D
D → d
Karena B → A dengan formulanya adalah menghilangkan A maka duplikasi B → A menghasilkan nullable baru yang perlu dihilangkan.

(c) Menghilangkan B → ε
Dengan cara menduplikasi BACa | BAa | BAa | Ba | namun menghilangkan B
S → BACa | BAa | BAa | Ba | ACa | Aa | Aa | a
B → AC | A | C 
A → dC | d
C → D
D → d

Langkah Kedua :
Penghilangan Produksi Unit
S → BACa | BAa | BAa | Ba | ACa | Aa | Aa | a
B → AC | A | C 
A → dC | d
C → D
D → d

Penggantian Berurutan : 
C → D = C → d
B → C = B → d
B → A = B → dc 

*Karena S memiliki Aturan Produksi yang sama, dapat dituliskan hanya 1 kali saja.
Aturan Produksi setelah Penyederhanaan : 
S → BACa | BAa | Ba | ACa | Aa | a
B → AC | dc | dC
A → dC | d
C → D
D → d

Langkah Ketiga :
Penghilangan Produksi Useless
S → BACa | BAa | Ba | ACa | Aa | a
B → AC | dC | d 

Kesimpulan :
a. S → BACa | ACa (C tidak memiliki penurunan menuju ke terminal maka dinyatakan useless)
b. S → BAa | Aa (A tidak memiliki penurunan menuju ke terminal maka dinyatakan useless)
b. B → AC | dC (A & C tidak memiliki penurunan menuju ke terminal maka dinyatakan useless)

Hasil Penyederhanaan Useless :
S → Ba | a
B → d
Video Penjelasan Soal Latihan 5 :


Komentar

Posting Komentar

Postingan populer dari blog ini

Desimal Positif & Negatif dan Konversi Biner

Gambar
Kali ini kita akan membahas bagaimana cara menghitung Desimal Positif dengan Desimal Negatif yang kemudian akan dikonversikan ke dalam bentuk Biner lalu dihitung desimal ke dalam bentuk biner, apakah sama dengan hasil ketika dalam bentuk Desimal. Sekilas Materi : Bentuk Komplemen dalam Biner 1. One Complement One complement berguna untuk membantu dalam mencari biner dari bentuk desimal negatif. Dioperasikan dengan 0011 Atau lebih simplenya 0 menjadi 1 dan 1 menjadi 0 tanpa mengubah nilai paling depan yang melambangkan tanda negatif (-). Contoh :    0001 0110           Yang tadinya 00010110 menjadi 00010110    0000 0011  ===========+      0001 1001 2. Two Complement Two complement adalah bilangan negatif direpresentasikan dengan cara menambahkan satu pada bentuk komplemen satu. Jika tadi di One Complement bernilai 00011001 Maka bentuk keduanya   00011001                 1 ===========+   00011010 Contoh 1: 1. Menjumlahkan Desimal Negatif dengan D
Baca selengkapnya

Memori Internal

Gambar
Memori Internal  Pengertian Memori Memori adalah bagian dari komputer tempat program–program dan data– data disimpan. Memori juga diartikan sebagai tempat informasi, dibaca dan ditulis, dimana terdapat berbagai jenis, teknologi, organisasi, unjuk kerja dan harga memori. Memory pada sistem komputer dapat dibedakan menjadi : 1. Internal memory 2. Eksternal memory Memory digunakan untuk menyimpan data atau program yang akan diproses oleh processor. Berdasarkan sifat dari data tersebut yang berhubungan dengan pemrosesan maka dapat di kategorikan: 1. Data yang sedang diproses. 2. Data yang akan diproses. 3. Data yang belum diproses. Contoh Memori Internal. Karakter Sistem Memori Karakteristik memori terbagi atas beberapa bagian yaitu: Tiga konsep Unit of Transfer yang saling berhubungan bagi internal memori : 1. Word Ukuran word biasanya sama dengan jumlah bit yang digunakan untuk merepresentasikan bilangan dan panjang instruksi. 2. Addressable Units Pa
Baca selengkapnya

Pohon Penurunan Tata Bahasa Bebas Konteks

Gambar
"Pohon Penurunan Tata Bahasa Bebas Konteks" Parsing Pohon (tree) adalah suatu graph terhubung tidak sirkuler, yang memiliki satu simpul (node) yang disebut akar dan dari situ memiliki lintasan ke setiap simpul. Pohon penurunan (derivation tree/parse tree) berguna untuk menggambarkan bagaimana memperoleh suatu string (untai) dengan cara menurunkan simbol-simbol variabel menjadi simbol-simbol terminal. Contoh Soal : 1.  S → AA A → AAA | a | bA | Ab Untai yang dicari : bbabaaba Jawaban : S => A A => b A A => bb A A => bba A => bba A AA => bba A AA => bbab A AA => bbaba A A => bbaba A bA => bbabaab A => bbabaaba Pohon Penurunan : 2. S → AB A → Aa | bB B → a | Sb Untai yang dicari : baabaab Jawaban : S => A B => Aa B => A aSb => b B aSb => baa S b => baa A Bb => baab BB b => baabaab Pohon Penurunan : 3. S → Ba | Ab A → Sa | Aab | a B → Sb | Bba | b Untai yang dicari : bbaaabb
Baca selengkapnya