Bentuk Normal Chomsky


Pengertian Bentuk Normal Chomsky

Bentuk normal Chomsky / Chomsky Normal Form  (CNF) merupakan salah satu bentuk normal yang sangat berguna untuk Context Free Grammar (CFG) . Bentuk normal Chomsky dapat dibuat dari sebuah tata bahasa bebas konteks yang telah mengalami penyederhanaan yaitu penghilangan produksi useless, unit, dan ε. Dengan kata lain, suatu tata bahasa bebas konteks dapat dibuat menjadi bentuk normal Chomsky dengan syarat tata bahasa bebas kontesk tersebut:

  • Tidak memiliki produksi useless
  • Tidak memiliki produksi unit
  • Tidak memiliki produksi ε

Bentuk normal Chomsky (Chomsky Normal Form, CNF) adalah Context Free Grammar (CFG) dengan setiap produksinya berbentuk :

 A BC atau A a.

Transformasi CFG ke CNF

Transformasi CFG ke CNF adalah transformasi berikut :

Transformasi CFG ke CNF

Transformasi CFG ke CNF

Aturan produksi dalam  bentuk normal Chomsky ruas kanannya tepat berupa sebuah terminal atau dua variabel.

Misalkan:

  • A → BC
  • A → b
  • B → a
  • C → BA | d

Pembentukan Bentuk Normal Chomsky

Langkah-langkah pembentukan  bentuk normal Chomsky  secara umum sebagai berikut:

  • Biarkan aturan produksi yang sudah dalam  bentuk normal Chomsky
  • Lakukan penggantian aturan produksi yang ruas kanannya memuat simbol terminal dan panjang ruas kanan > 1
  • Lakukan penggantian aturan produksi yang ruas kanannya memuat > 2 simbol variabel
  • Penggantian-penggantian tersebut bisa dilakukan berkali-kali sampai akhirnya semua aturan produksi dalam  bentuk normal Chomsky
  • Selama dilakukan penggantian, kemungkinan kita akan memperoleh aturan-aturan produksi baru, dan juga memunculkan simbol-simbol variabel baru

Bisa dilihat tahapan-tahapan tersebut pada gambar berikut:

Langkah-langkah pembentukan  bentuk normal Chomsky

Langkah-langkah pembentukan bentuk normal Chomsky

Contoh, Context Free Grammar ( kita anggap CFG pada bab ini sudah mengalami Penyederhanaan CFG ):

S → bA | aB
A → bAA | aS | a
B → aBB | bS | b

Aturan produksi yang sudah dalam  bentuk normal Chomsky:

A → a
B → b

Dilakukan penggantian aturan produksi yang belum bentuk normal Chomsky (‘=>’ bisa dibaca berubah menjadi):

S → bA => S → P1A
S → aB => S → P2B
A → bAA =>A → P1AA => A → P1P3
A → aS => A → P2S
B → aBB => B → P2BB => B → P2P4
B → bS => B → P1S

Terbentuk aturan produksi dan simbol variabel baru:

P1 → b
P2 → a
P3 → AA
P4 → BB

Hasil akhir aturan produksi dalam bentuk normal Chomsky :

A → a
B → b
S → P1A
S → P2B
A → P1P3
A → P2S
B → P2P4
B → P1S
P1 → b
P2 → a
P3 → AA
P4 → BB

P1 = P, P2 =Q, P3 =R, P4 =T, sehingga aturan produksinya menjadi:

S → PA
S → QB
A → PR
A → QS
A → a
B → QT
B → PS
B → b
P → b
Q → a
R → AA
T → BB

Contoh Lain:

Tata bahasa bebas konteks:

S →aB | CA
A →a | bc
B →BC | Ab
C →aB | b

Aturan produksi yang sudah dalam bentuk normal Chomsky :

S → CA
A → a
B → BC
C → b

Penggantian aturan produksi yang belum dalam bentuk normal Chomsky:

S → aB => S → P1B
A → bc => A → P2P3
B → Ab => B → A P2
C → aB => C → P1B

Terbentuk aturan produksi dan simbol variabel baru:

P1 → a
P2 → b
P3 → c

Hasil akhir aturan produksi dalam  bentuk normal Chomsky :

 S → CA
A → a
B → BC
C → b
S → P1B
S → P2P3
B → A P2
C → P1B
P1 → a
P2 → b
P3 → c

Misalkan P1 = D, P2 = E, P3 =F, maka aturan produksinya menjadi:

S → CA
A → a
B → BC
C → b
S → DB
S → EF
B → AE
C → DB
D → a
E→ b
F→ c

Contoh Transformasi CFG ke CFN lainya:

CFG:

S → aAB | ch | CD
A → dbE | eEC
B → ff | DD
C → ADB | aS
D → i
E → jD

Aturan produksi yang sudah dalam bentuk normal Chomsky :

S → CD
B → DD
D → i

Penggantian aturan produksi:

S → aAB => S → P1P2
S → ch => S → P3P4
A → dbE => A → P5P6
A → eEC => A → P8P9
B → ff => B → P10P10
C → ADB => C → AP11
C → aS => C → P1S
E → jD => E → P12D

Terbentuk aturan produksi baru:

P1 → a
P2 → AB
P3 → c
P4 → h
P5 → d
P6 → P7E
P7 → b
P8 → e
P9 → EC
P10 → f
P11 → DB
P12 → j

Hasil akhir dalam bentuk normal Chomsky:

S → CD
B → DD
D → i
S → P1P2
S → P3P4
A → P5P6
A → P8P9
B → P10P10
C → AP11
C → P1S
E → P12D
P1 → a
P2 → AB
P3 → c
P4 → h
P5 → d
P6 → P7E
P7 → b
P8 → e
P9 → EC
P10 → f
P11 → DB
P12 → j

Materi yang berhubungan:

Download : [pdf] Bentuk Normal Chomksy

One thought on “Bentuk Normal Chomsky

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