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:

Penghilangan produksi ε.
Penghilangan produksi unit.
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

Biarkan aturan produksi yang telah dalam bentuk CNF
Lakukan penggantian aturan produksi yang luas kanannya memuat simbol terminal dan panjang ruas kanan > 1
Lakukan penggantian aturan produksi yang ruas kannnya memuat > 2 simbol variabel.
Penggantian-penggantian tersebut bisa dilakukan berkali-kali sampai akhirnya semua aturan produksi dalam bentuk CNF.
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

S → aB	=>	S → P₁B
A → bc	=>	A → P₂P₃
B → Ab	=>	B → AP₂
C → aB	=>	C → P₁B

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

Materi-materi yang Masih Berkaitan

Materi Induk