MODUL 12: BENTUK-BENTUK SEDERHANA DAN BENTUK-BENTUK NORMAL

Diktat Kuliah: Bentuk-bentuk Sederhana dan Bentuk-bentuk Normal

MODUL 12: BENTUK -BENTUK S EDERHANA DAN BENTUK -BENTUK NORMAL P ENDAHULUAN Dalam bahasan berikut akan dilakukan cara-cara untuk “memperbaiki” grammar tanpa adanya perubahan penting dari bahasa yang dihasilkannya: • Dengan menghilangkan produksi-Λ Λ dan produksi unit • Dengan pembakuan produksi sehingga mengikuti suatu Bentuk Normal Chomsky (CNF) Produksi-Λ adalah produksi berbentuk A → Λ, dan produksi unit adalah produksi berbentuk A → B. Apabila tidak ada produksi-Λ maka pada setiap kemungkinan penurunan α ⇒ β selalu terjadi |α | ≤ |β|. Apabila tidak ada produksi unit maka jika |α| = |β|, berarti yang terjadi satu variabel tersubstitusi oleh satu simbol (terminal). Dalam bentuk grammar demikian maka analisis-analisis teoritis dapat lebih mudah dilakukan. Misalnya, jika l panjang string α dan t jumlah terminal di dalamnya, agar kedua produksi tersebut tidak ada maka l+t harus bertambah pada setiap langkah penurunan. Pada penurunan S ⇒* x, di awal penurunan l+t = 1 (untuk S), dan di akhir penurunan l+t = 2k jika |x| = k. Jika kedua produksi tersebut tidak ada maka dapat dipastikan paling banyak terjadi 2k-1 penurunan (Jika lebih banyak dari itu pastilah terjadi salah satu produksi tersebut).

MENGHILANGKAN P RODUKSI-Λ Ide dasarnya adalah jika dalam grammar terdapat produksi C → Λ maka kem udian kita cari produksi A → β dimana β berisikan C, lalu, hilangkan C→Λ dan buat produksi baru A → β 1 yaitu β tanpa adanya C. Kalau C muncul lebih dari satu kali di β maka semua produksi berbentuk A → β k dibuat dengan β k merupakan β dengan mensubsitusi secara bergantian setiap C.

Author: Suryana Setiawan, MSc., Fak. Ilmu Komputer UI

A → Sa C → Λ |a maka C → Λ dapat dihilangkan disertai dengan menambahkan S → AC (C pertama dihilangkan), S → CA (C kedua dihilangkan) dan S → A (kedua C dihilangkan sehingga menjadi S → CAC | AC | CA | A A → SA C→a Masih terdapat variabel yang potensial menjadi Λ akibat penghilangan variabel tsb misalnya A → BC sementara B → Λ dan C → Λ, maka akan menjadi terbentuk A → Λ. Untuk lebih sistematis pembahasan algoritma penghapusan produksi-Λ ini maka perlu dibuatkan definisi berikut ini.

Variabel Nullable Variabel nullable dalam CFG G = (V, Σ , S, P) di definisikan sbb. • variabel A adalah nullable jika dalam P terdapat A →Λ • variabel A nullable jika dalam P terdapat A → B1B2…Bn dan semua B1, B2, …, Bn nullable. • Tidak ada variabel lain yang nullable. Jadi variabel nullable adalah variabel yang memiliki, termasuk yang potensial nantinya memiliki, produksi-Λ. Definisi tersebut dapat diterjemahkan dalam bentuk algoritma pencarian variabel nullable dalam G = (V, Σ, S, P) sebagai berikut ini.

Algoritma FindNull

N0 = {A ∈ V | P berisikan produksi A →Λ} do i = i+1 Ni = Ni-1 ∪ {A ∈ V | P berisikan produksi A →α untuk α ∈N*} while (Ni - Ni-1) ≠ ∅

Contoh: S → CAC

Update Version 1.2.1, printed at 3:01 PM , 10/30/01

page 1 of 5


Contoh pada grammar S → ABCE E → BDA A → CD B → Cb C → a|Λ D → bD | Λ Mula-mula N0 = {C, D} karena terdapat C → Λ dan D → Λ, kemudian N 1 = {A, C, D} karena terdapat A → CD, serta C, D ∈ N 0. Karena tidak ada penambahan variabel baru pada N2 maka himpunan variabel nullabel untuk grammar tsb adalah {A, C, D }.

Algoritma Menghilangkan Produksi-Λ Λ Dengan algoritma tersebut maka algoritma menghilangkan produksi-Λ dari CFG G = (V, Σ, S, P) menjadi CFG G1 = (V, Σ , S, P1) dapat disusun sebagai berikut. • Inisialisasi P1 = P • Mencari variabel-variabel nullable dalam V dengan algoritma FindNull • Untuk setiap produksi A →α dalam P tambahkan P1 setiap bentuk produksi yang dapat dicapai dari produksi ini dengan menghapuskan dari α kemunculan satu atau lebih variabel nullable. • Hapus semua produksi-Λ dari P1 • Jika ada hapus produksi berbentuk A → A • Jika ada hapus duplikasi (beberapa produksi yang sama ambil satu dan hapus yang lain). Dari contoh di sebelumnya setelah mendapatkan variabel nullable {A, C, D } maka sejumlah aturan produksi baru ditambahkan sbb. Pada S → ABCE terdapat A dan C, sehingga S → ABCE | BCE | ABE | BE Pada E → BDA terdapat D dan A, sehingga E → BDA | DA | BD | D Pada A → CD terdapat C dan D, sehingga A → CD | C | D | Λ Dan seterusnya. Setelah menghilangkan semua produksi-Λ maka dip eroleh S → ABCE | BCE | ABE | BE E → BDA | DA | BD | D A → CD | C | D



B → Cb | b C→a D → bD Jika S adalah nullable maka grammar G1 yang dihasilkan algoritma di atas tidak persis sama dengan grammar G semula karena L(G 1) = L(G) – {Λ}. Untuk menjaga bahw a grammar tetap mendefinisikan grammar yang sama, jika S adalah nullable maka S → Λ dalam P1 (jadi terdapat pengecualian adanya produksi-Λ untuk S). Tanpa itu, maka secara umum dapat dikatakan bahwa L(G1) = L(G ) – {Λ}. Untuk contoh di atas karena S bukan nullable maka grammar yang dihasilkan mendefinisikan bahasa yang tepat sama dengan yang didefinisikan grammar semula.

MENGHILANGKAN P RODUKSI UNIT Ide dasar: untuk menghilangkan produksi A → B sementara terdapat B →α maka dibuat A → α sebagai gantinya. Namun, karena bisa terdapat rantai produksi unit A → B, B → C, … maka perlu dibuatkan terlebih dahulu definisi berikut ini.

Derrivabilitas

Pada suatu CFG G = {V, Σ , S, P}, dan setiap A, B, C ∈ V • Jika A → B suatu produksi dalam P maka B disebut A-derrivable. • Jika C adalah A-derrivable, dan jika C → B suatu produksi dalam P maka B juga A-derrivable. • Tidak ada variabel lain dalam V yang A-derrivable. Contoh pada grammar S → S+T | T T → T*F | F F → (S) | a Maka T dan F adalah S-derivable.

page 2 of 5


Dengan definisi tersebut maka algoritma penghilangan produksi unit dapat disusun sebagai berikut.

Algoritma Menghilangkan Produksi Unit

Dari grammar G = (V, Σ, S, P) yang tidak memiliki produksi-Λ, grammar G1 = (V, Σ, S, P1) yang tidak memiliki produksi unit dapat dibuat sebagai berikut. 1. Inisialisasi P1 dengan P. 2. Untuk setiap A ∈ V temukan A-derrivable. 3. Untuk setiap pasangan (A, B) dimana B adalah A-derrivable dan setiap produksi B → α yang bukan produksi unit, tambahkan A → α dalam P1. 4. Hapus semua produksi unit dari P1. Perhatikan bahwa algoritma ini mensyaratkan grammar G sudah tidak memiliki produksi-Λ. Untuk grammar sembarang maka sebelum dihilangkan produksi unitnya, perlu di hilangkan dulu produksi-Λ-nya. Mengingat bahwa setelah produksi-Λ dihilangkan berlaku L(G 1) = L(G) – {Λ}, maka setelah penghilangan produksi unit sifat itu juga tetap berlaku. Untuk contoh sebelumnya himpunan S-derrivable = {F, T}, himpunan Tderivable = {T}, himpunan F-derrivable = {}. Dari langkah ke-3 diperoleh S → S+T | T | T*F | F | (S) | a T → T*F | F | (S) | a F → (S) | a Dari langkah-4, maka tersisa aturan-aturan produksi: S → S+T | T*F | (S) | a T → T*F | (S) | a F → (S) | a

BENTUK NORMAL CHOMSKY (CNF) Seperti pada pembahasan di awal bahwa penghilangan kedua macam produksi yang telah dibahas adalah untuk mendapatkan grammar yang lebih mudah dianalisis secara teoritis. Hal ini ditunjukkan dengan jumlah langkah pada



penurunan S ⇒* x yang tidak akan lebih banyak dari 2|x| - 1. Selain batas atas jumlah langkah penurunan, juga terkadang batas bawah jmlah penurunan diperlukan, bahkan kalau bisa jumlah langkah adalah fungsi dari |x|. Bentuk normal Chomsky adalah bentuk grammar yang memastikan bahwa jumlah langkah penurunan pada S ⇒* x tepat 2| x| - 1.

Definisi CNF Suatu CNF G berada dalam bentuk normal Chomsky (CNF/Chomsky Normal Form) apabila setiap produksi mengambil salah satu dari dua pola: A → BC A→ a Dimana A, B, C adalah variabel dan a adalah simbol. Algoritma Transformasi ke CNF Sebelumnya perlu dilakukan penghapusan produksi-Λ dan produksi unit terlebih dahulu pada grammar G yang akan ditransformasikan. Selanjutnya setelah diperoleh grammar G1 tanpa kedua produksi tersebut, G2 = (V, Σ, S, P2) diperoleh dalam dua tahap. 1. Setiap produksi dibuat untuk berada dalam format A → B1B2…Bk , dengan k ≥ 2 dan Bi ∈ V2, atau A → a, untuk a ∈ Σ . Untuk itu, jika terdapat A → α dan |α| ≥ 2 di dalam α terdapat simbol a maka dibuat suatu variabel baru misalnya Xa dan Xa → a ke dalam P2 serta mengganti setiap a dalam α dengan Xa. Kecuali, kalau sebelumnya sudah ada produksi A → a, maka Xa dan Xa → a tidak perlu dibuat, tapi setiap a dalam α diganti A. 2.

Setiap produksi A → B1B2B3… Bk-1Bk dengan k > 2 diganti dengan sejumlah produksi yang ekivalen yang masing-masing berbentuk X → YZ. Penggantian yang bisa dilakukan adalah dengan mengganti B2B3…Bk dengan variabel baru X1 dan menambahkan X1 → B2X2, X 2 → X3B3, … Xk-2 → Bk-1Bk .

Untuk contoh sebelumnya setelah menghilangkan produksi unit, grammar: S → S+T | T*F | (S) | a

page 3 of 5


T → T*F | (S) | a F → (S) | a dapat dikonversi ke dalam CNF sbb. Step 1 menghasilkan S → SX+ T | TX*F | X(SX) | a T → TX*F | X (SX) | a F → X(SX) | a X+ → + X* → * X( → ( X) → ) Step 2 menghasilkan S → SZ1 | TZ2 | X3Z3 | a T → TZ2 | X 3Z3 | a F → X3Z3 | a Z1 → X1T Z2 → X2F Z3 → SX4 X1 → + X2 → * X3 → ( X4 → )


A → aAb | Λ C → aC | a D → aDa | bDb | Λ Variabel-variabel nullable adalah A, D. Proses mengilangkan produksi-Λ pada G menghasilkan G1 dengan produksi-produksi: S → AACD | ACD | AAC | CD | AC | C A → aAb | ab C → aC | a D → aDa | bDb | aa | bb Penghilangan produksi unit pada G1 menghasilkan G2 dengan produksi-produksi: S → AACD | ACD | AAC | CD | AC | aC | a A → aAb | ab C → aC | a D → aDa | bDb | aa | bb Tahap pertama konversi ke CNF menghasilkan G 3 dengan produksi-produksi: S → AACD | ACD | AAC | CD | AC | XaC | a A → XaAXb | XaXb C → XaC | a D → XaDXa | XbDXb | XaXa | XbXb Xa → a Xb → b

Yang sudah dalam CNF. Mengingat bahwa setelah produksi-Λ dihilangkan dari G menjadi G1, berlaku L(G1) = L(G ) – {Λ}, maka setelah dalam CNF menjadi G 2 sifat itu juga tetap berlaku. Yang artinya, jika Λ ∈ L(G ) dan G grammar semula dikonversi ke dalam CNF menjadi G 2 maka Λ ∉ L(G2).

Contoh: diberikan CFG G dengan produksi-produksi S → AACD


Tahap kedua konversi ke CNF menghasilkan G 4 dengan prduksi-produksi: S → AT 1 | AU 1 | AV1 | CD | AC | XaC | a A → XaW1 | XaXb C → XaC | a D → XaY1 | XbZ1 | XaXa | XbXb Xa → a Xb → b T1 → AT 2 T2 → CD

page 4 of 5



U1 → CD V1 → AC W1 → AXb Y1 → DXa Z2 → DXb


page 5 of 5

MODUL 12: BENTUK-BENTUK SEDERHANA DAN BENTUK-BENTUK NORMAL

Recommend Documents