Sabtu, 28 Mei 2011

PENYEDERHANAAN TATA BAHASA BEBAS KONTEKS (CFG)

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.



Menghilangkan Produksi Useless
Produksi Useless didefinisikan sebagai berikut :

  • Poduksi yang memuat simbol variable yang tidak memiliki penurunan yang akan menghasilkan terminal-terminal seluruhnya
  • 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


Menghilangkan 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. untuk menyederhanakan produksi unit, dilakukan penggantian aturan produksi unit tersebut.

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


Menghilangkan Produksi ε
Produksi ε adalah produksi dalam bentuk α -> ε atau bisa dianggap sebagai produksi kosong (empty).
penghilangan produksi  ε dilakukan dengan melakukan penggantian produksi yang memuat variable yang bisa menuju produksi ε, atau disebut Nullable.

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 satu2nya dari C. maka qita ganti S -> Cd menjadi S -> d. kemudian produksi C -> ε kita hapus.
Hasil penyederhanaannya adalah :
S -> aB | d
A -> d

Dalam prakteknya ketiga penyederhanaan tersebut dilakukan bersama pada suatu tata bahasa bebas konteks, yang nantinya menyiapkan tata bahasa bebas konteks tersebut untuk diubah kedalam suatu bentuk normal Chomsky (CNF).
Urutan dari penyederhanaan aturan produksi bebas konteks adalah sebagai berikut :
  1. Hilangkan produksi ε
  2. Hilangkan produksi unit
  3. Hilangkan produksi useless

Smoga bermanfaat. jika ada yang kurang jelas dan sulit difahami, silahkan tinggalkan comment...;-)
Sumber : Dari berbagai sumber

10 Comment:

Anonim mengatakan...

klo soalnya kaya gni hilangkan produksi ε :
S->AB
A->aA|abB|aCa
B->bA|BB|ε
C->ε
D->dB|BCB

sh3susan mengatakan...

variable yg nullable dari soal ini ada 2 yaitu variable C dan B.C bisa langsung dihilangkan krn C->ε merupakan penurunan satu2nya. untuk variable B krn B->ε bukan penurunan satu2nya (masih ada B->bA|BB) maka harus dilakukan penggantian.

Rendi mengatakan...

Ada soal yang lebih rumit nih...

Jika diketahui CFG, sbb :

S --> kA | BAj | m
A --> Bb | a | ε
B --> bS | cA | d

Coba lakukan langkah2 penyederhanaan CFG !

Bagaimanakah penyelesaiannya ??? :)

Mohon penjelasannya ya ! :)

Anonim mengatakan...

klo soal nya kaya gini ;

Sederhanakan pada tata bahasa bebas konteks

S -> aA | A | C
A -> a
B -> aa
C -> aCb | ε

(penghilangan produksi ε, unit dan userless)

Susana Dwi Yulianti mengatakan...

@Randi: klo diliat soalnya,proses yang dilakukan cukup menghilangkan produksi ε karna dari soal tersebut tidak ada produksi unit maupun produksi useless. hasil penyederhanaannya seperti berikut:
S-> kA | k | BAj | Bj | m
A-> Bb | a
B-> bS | cA | c | d

Susana Dwi Yulianti mengatakan...

untuk penyederhanaan soal:
S -> aA | A | C
A -> a
B -> aa
C -> aCb | ε
hasil menghilangkan produksi ε:
S-> aA | A | C
A-> a
B-> aa
C-> aCb
dari penyederhanaan diatas masih terdapat produksi unit di aturan produksi S dan dapat disederhanakansebagai berikut:
S-> aA | a | aCb
A-> a
B-> aa
C-> aCb
selanjutnya hilangkan produksi useless pada aturan produksi C karna aturan produksi C tidak memiliki aturan produksi yang menuju terminal. hasil penyederhanaan akhir adalah:
S-> aA | a
A-> a
B-> aa

supratikno aji mengatakan...

Jadi urutan penyederhanaan yang benar itu Empty, Unit, Useless, normal chomsky. Begitukah mbak ? Trims ya buat ilmunya ^-^

Susana Dwi Yulianti mengatakan...

iya betul mas aji, tp normal chomsky itu bkn termasuk kedalam urutan penyederhanaan. tetapi goal dari penyederhanaan adalah untuk membentuk CNF (chomsky normal form) begitu yg saya tangkap menurut literatur yg saya baca :)

Anonim mengatakan...

mohon bantuan
gmn cara ngerjainnya

1.Diberikan CFG G = sebagai berikut:

dan himpunan string W sebagai berikut:

a.Tuliskan semua string di dalam W yang merupakan anggota dari L(G)!
b.Untuk setiap string yang merupakan jawaban pada poin (a) di atas, tuliskan leftmost-derivation-nya!

Susana Dwi Yulianti mengatakan...

mana CFG nya ya?ko ga ada? :D

Poskan Komentar