KONVERSI CFG MENJADI CNF

CNF atau Chomsky Normal Form merupakan salah satu bentuk normal yang sangat berguna untuk Context Free Grammar (CFG). CNF dapat dibuat dari CFG yang telah disederhanakan, yaitu eliminasi ɛ-production, eliminasi unit production dan eliminasi useless symbol. Pada CNF terdapat aturan, pada ruas kanannya yaitu hasil produksi, harus dalam bentuk 1 terminal atau 2 variable, contohnya adalah sebagai berikut:

• X → YZ
• Y → p
• Z → q

Berikut adalah langkah – langkah pembentukan CNF dari CFG yang telah disederhanakan:

• Hasil produksi yang sudah sesuai aturan CNF tidak perlu diubah atau dihilangkan
• Jika terdapat hasil produksi yang terdiri dari lebih dari 1 terminal maka terminal tersebut harus diganti kedalam bentuk variable
• Jika terdapat lebih dari 2 variable maka 2 variable paling belakang harus diganti lagi menjadi 1 variable
• Pergantian – pergantian tersebut bisa dilakukan berkali – kali sampai akhirnya sudah memenuhi aturan hasil produksi pada CNF
• Pada saat dilakukan pergantian –pergantian tersebut, maka kita akan memperoleh aturan – aturan produksi baru.

Berikut contoh Perubahan bentuk CFG menjadi CNF :

A → cAB | ab
B →  aC | b | BC
C →  bC| a

Cara pengerjaan:

• cAB = c diganti menjadi D, lalu menjadi CAB, lalu AB diganti menjadi E, dan menjadi AE
  cAB menjadi AE, dengan tambahan produksi baru yaitu: D → c dan E → AB
• ab = A diganti menjadi F, b diganti diganti menjadi G
  ab menjadi FG, dengan tambahan produksi baru yaitu: F → a dan G → b
• aC = karena F → a, maka aC menjadi FC
• bC = karena G → b, maka bC menjadi GC

Final Result :

A → AE | FG
B →  FC | b | BC
C →  GC| a
D → c
E → AB
F → a
G → b