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