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
Tidak ada komentar:
Posting Komentar