BENTUK NORMAL CHOMSKY

BENTUK NORMAL CHOMSKY

(CHOMSKY NORMAL FORM / CNF)

• Merupakan salah satu bentuk normal yang sangat berguna untuk CFG

• Bentuk normal Chomsky dibuat dari CFG yang telah mengalami penyederhanaan yaitu penghilangan produksi useless, unit, dan ε.

• Aturan produksi dalam bentuk normal Chomsky adalah ruas kanannya tepat berupa sebuah terminal atau 2 variabel, misal :

A 􀃆 BC

A 􀃆 b

B 􀃆 a

C 􀃆 BA | d

• Langkah-langkah pembentukan bentuk normal Chomsky :

Biarkan yang sudah CNF

• Contoh : Berikut ini CFG yang sudah mengalami penyederhanaan

S 􀃆 Ba | Ab

A 􀃆 Baa | As | a

B 􀃆 Abb | Bs | b

Aturan produksi yang sudah dalam bentuk normal Chomsky (CNF) :

A 􀃆 a

B 􀃆 b

Dilakukan penggantian aturan produksi yang belum bentuk normal Chomsky :

S 􀃆 Ba menjadi S 􀃆 P1A

S 􀃆 Ab menjadi S 􀃆 P2B

A 􀃆 Baa menjadi A 􀃆 P1AA menjadi A 􀃆 P1P3

A 􀃆 As menjadi A 􀃆 P2S

B 􀃆 Abb menjadi B 􀃆 P2BB menjadi B 􀃆 P2P4

B 􀃆 Bs menjadi B 􀃆 P1S

Sehingga 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 􀃆 P2 P4

B 􀃆 P1S

CFG yang sudah disederhanakan

Penggantian simbol terminal pada aturan produksi yang ruas kanan > 1

Buat variabel dan aturan produksi baru bila perlu

CNF

Penggantian aturan produksi yang simbol variabel > 2

31

P1 􀃆 b

P2 􀃆 a

P3 􀃆 AA

P4 􀃆 BB

• Contoh : Berikut ini CFG yang sudah mengalami penyederhanaan

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 menjadi S 􀃆 P1B

A 􀃆 bc menjadi S 􀃆 P2P3

B 􀃆 Ab menjadi B 􀃆 AP2

C 􀃆 Ab menjadi 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 􀃆 AP2

C 􀃆 P1B

P1 􀃆 a

P2 􀃆 b

P3 􀃆 c

• Contoh 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 menjadi S 􀃆 P1P2

S 􀃆 ch menjadi S 􀃆 P3P4

32

A 􀃆 dbE menjadi A 􀃆 P5P6

A 􀃆 Eec menjadi A 􀃆 P8P9

B 􀃆 ff menjadi B 􀃆 P10P10

C 􀃆 ADB menjadi C 􀃆 AP11

C 􀃆 As menjadi C 􀃆 P1S

E 􀃆 Jd menjadi 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