Chomsky Normal Form (CNF)

CNF atau Chomsky Normal Form merupakan salah satu bentuk normal dari Context Free Grammar (CFG) atau Tata Bahasa Bebas Konteks.

CNF dapat dibuat dari CFG yang telah disederhanakan melalui:

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

Untuk menyederhanakan CFG bisa dilihat di sini. Menyederhanakan CFG.

Aturan Produksi Chomsky Normal Form

1. Ruas kanannya tepat berupa sebuah simbol terminal atau dua variabel.

α → β

α = 1 non-terminal

β = 1 terminal atau dua variabel.

Contoh: A → b, B → CC, atau C → DD | e

2. Jika terdapat lebih dari satu simbol terminal maka harus dilakukan penggantian dan juga jika terdapat lebih dari dua simbol variabel harus dilakukan perubahan.

Langkah Pembentukan CNF

1. Biarkan aturan produksi yang telah dalam bentuk CNF
2. Lakukan penggantian aturan produksi yang luas kanannya memuat simbol terminal dan panjang ruas kanan > 1
3. Lakukan penggantian aturan produksi yang ruas kannnya memuat > 2 simbol variabel.
4. Penggantian-penggantian tersebut bisa dilakukan berkali-kali sampai akhirnya semua aturan produksi dalam bentuk CNF.
5. Selama dilakukan penggantian, kemungkinan kita akan memperoleh aturan-aturan produksi baru, dan juga memunculkan simbol-simbol baru.

Contoh Pembentukan Chomsky Normal Form

Misalnya ada aturan produksi CFG yang diasumsikan telah disederhanakan sebagai berikut:

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

Langkah pembentukan CNF adalah sebagai berikut:

1. Biarkan Aturan Produksi yang Telah dalam Bentuk CNF

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

2. Lakukan Penggantian Aturan Produksi yang Belum CNF

• S → aB
• A → bc
• B → Ab
• C → aB

3. Terbentuk Aturan Produksi Baru

• P₁ → a
• P₂ → b
• P₃ → c

4. Hasil Akhir dalam Bentuk CNF

• S → CA
• S → P₁B
• A → a
• A → P₂P₃
• B → BC
• B → AP₂
• C → b
• C → P₁B

Referensi

• Wikipedia
• PAKKODING

Materi-materi yang Masih Berkaitan

• Membuat Pohon Penurunan dari CFG
• Menyederhanakan CFG

Materi Induk

• Teknik Informatika
• Teori Bahasa dan Otomata