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

14 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

Uccank Hacker mengatakan...

bro kalo soalnya kaya gini gimana..??
S-> A
A-> aA| ε
B-> bA

hafiz ahmad mengatakan...

kalo soalnya gini gmn :

S -> AmH | F | a
A -> HaS | h | ε
H -> Aa | i | ε
F -> c

lakukanlah penyederhanaan CFG itu gmn ya mba ?

Susana Dwi Yulianti mengatakan...

Untuk soal berikut:
S-> A
A-> aA| ε
B-> bA
saya coba jawab ya, Penyederhanaannya kaya gini:
1. Menghilangkan produksi useless:
A merupakan variable nullable tapi hasil produksi ga cuma 1 tapi masih ada jadi hasilnya: A->a Untuk produksi A-> ε dihilangkan
Efeknya untuk aturan produksi lainnya adalah S->A dihilangkan dan B->bA menjadi B->b
Jadi, sisa aturan produksinya yaitu:
A->a
B->b
2. Menghilangkan produksi unit: tidak ada produksi unit sehingga bias dilewati untuk tahap ini
3. Menghilangkan produksi useless: tidak ada produksi unit sehingga bias dilewati untuk tahap ini

Susana Dwi Yulianti mengatakan...

Untuk soal berikut:
S -> AmH | F | a
A -> HaS | h | ε
H -> Aa | i | ε
F -> c
saya coba jawab ya, Penyederhanaannya kaya gini:
1. Menghilangkan produksi useless:
Variable nullable nya A dan H jadi hasil penghilangan produksi useless nya produksinya yaitu:
S -> AmH | F | a => A->mH | F | a
A -> HaS | h | ε => A->a | h
H -> Aa | i | ε => H->a | i
F -> c
2. Menghilangkan produksi unit:
Produksi unitnya ada satu yaitu :
A-> F => A->c
3. Menghilangkan produksi useless:
F->c merupakan produksi yang redudan, jadi bias dihilangkan.
Jadi hasil penyederhanaanya adl:
A -> mH | c | a
A -> a | h
H -> a | i

Poskan Komentar