Penyederhanaan Context Free Grammar (CFG)


Penyederhanaan Context Free Grammar (CFG)bertujuan untuk melakukan pembatasan sehingga tidak menghasilkan pohon penurunan yang memiliki kerumitan yang tak perlu atau aturan produksi tak berarti.

Missal :

  • S → AB | a
  • A → a

Kelemahanya adalah aturan produksi S → AB tidak berarti karena B tidak memiliki penurunan.

Penyederhanaan CFG dapat di lakukan dengan 3 cara :

  1. Penghilangan produksi useless
  2. Penghilangan produksi unit
  3. Penghilangan produksi Є

Penghilangan Produksi Useless

Definisinya sbb:

  • Produksi yang memuat simbol 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.

Contoh :

  • S → aSa | Abd | Bde
  • A → Ada
  • B → BBB |a

Langkah penyederhanaannya :

  1. Hilangkan aturan yang tidak menuju terminal.
  2. Hapus anggota S yang mengandung simbol himpunan ke terminal yang tidak berguna
  3. Hilangkan Redundan ( Anggota yang tidak ada di S dan Sebaliknya )

Maka, hasil penyederhanaanya adalah sbb :

  • S → aSa | Bde
  • B → BBB | a

Contoh lain :

  • S → Aa | B
  • A → ab | D
  • B → b | E
  • C → bb
  • E → aEa

 

Produksi yang useless adalah :

  • A → D
  • C → bb
  • E → aEa
  • B → E

Hasil akhir dari penyederhanaanya adalah :

  • S → Aa | B
  • A → ab
  • B → b

Penghilangan Produksi Unit

Definisi sbb :

Produksi unit adalah produksi dimana ruas kiri dan kanan aturan produksi hanya berupa satu simbol variabel, misalkan : A → B, C → D. Keberadaanya membuat tata bahasa memiliki kerumitan yang tak perlu, maka bisa dihilangkan.

 

Langkah penyederhanaanya :

  • Jabarkan masing-masing himpunan
  • Sederhanakan ruas kiri dan kanan yang hanya berupa variabel simbol sama
  • Hapus simbol variabel yang tidak berguna / tidak mempunyai turunan

Contoh suatu CFG sbb :

  • S → Sb
  • S → C
  • C → D
  • C → ef
  • D → dd

Jabarkan penurunan masing – masing himpunan :

  • C → D => C → dd
  • S → C => S → dd | ef

Maka hasilnya adalah sbb :

  • S → Sb
  • S → dd | ef
  • C → dd
  • C → ef
  • D → dd

Penghilangan Produksi Empty ( Є )

Definisi produksi empty adalah produksi kosong, (dengan bentuk α → Є) penghilangan dapat dilakukan dengan penggantian produksi yang memuat variabel yang menuju ke Є.

Langkah Penyerdehanaan CFG

  •  Hilangkan simbol yang terdapat empty ( Є ) dalam himpunan produksi
  • Simbol variabel tidak di hapus jika terdapat cabang terminal / variabel yang saling berhubungan
  • Buat himpunan dengan simbol yang dihilangkan dan yang tidak

Contoh :

  • S → bcAd
  • A → e

Maka variabel A bisa di hilangkan, sehingga menjadi :

  • S → bcd

Kasus lain :

  • S → bcAd
  • A → bd | Є

Maka hasilnya akan menjadi :

  • S → bcAd | bcd
  • A → bd

Karena A → Є bukan satu-satunya produksi dari A

 

Kasus lainya :

  • S → Ab | Cd
  • A → d
  • C → Є

Hasil penyederhanaan CFG sebagai berikut :

  • S → Ab | d
  • A → d

Contoh lain :

  • S → dA | Bd
  • A → bc
  • A → Є
  • B → c

Hasil penyederhanaan CFG sebagai berikut :

 

  • S → dA | Bd
  • A → bc
  • B → c

 

Contoh lainya :

  • S → AaCD
  • A → CD | AB
  • B → b | Є
  • C → d | Є
  • D → Є

 Hasil penyederhanaan CFG sebagai berikut :

 

  • S → AaC | aC |Aa | a
  • A → C | AB | A | B
  • B → b
  • C → d

Materi Terkait:

Iklan

2 thoughts on “Penyederhanaan Context Free Grammar (CFG)

  1. numpang nanya:
    Untuk soal:
    S → AaC | aC |Aa | a
    A → C | AB | A | B
    B → b
    C → d

    bukannya hasilnya seperti ini ya:
    S -> AaCD | AaC
    A -> AB | C | A
    B -> b
    C -> d

    Pertanyaan 1:
    dari jawaban yg anda berikan ada rule A -> C | AB | A | B, rule yang A -> B didapat dri mana? bknkah tidak ada peluang A -> Є ?

    Pertanyaan 2:
    S -> AaCD, mengapa AaCD dihilangkan, bknnya C bukan hanya memproduksi Є tpi juga C-> d , sehingga tidak bisa dihilangkan?

Tinggalkan Balasan

Isikan data di bawah atau klik salah satu ikon untuk log in:

Logo WordPress.com

You are commenting using your WordPress.com account. Logout / Ubah )

Gambar Twitter

You are commenting using your Twitter account. Logout / Ubah )

Foto Facebook

You are commenting using your Facebook account. Logout / Ubah )

Foto Google+

You are commenting using your Google+ account. Logout / Ubah )

Connecting to %s