Bentuk normal Chomsky / Chomsky Normal Form (CNF) merupakan salah satu bentuk normal yang sangat berguna untuk Context Free Grammar (CFG) . Bentuk normal Chomsky dapat dibuat dari sebuah tata bahasa bebas konteks yang telah mengalami penyederhanaan yaitu penghilangan produksi useless, unit, dan ε. Dengan kata lain, suatu tata bahasa bebas konteks dapat dibuat menjadi bentuk normal Chomsky dengan syarat tata bahasa bebas kontesk tersebut:
Bentuk normal Chomsky (Chomsky Normal Form, CNF) adalah Context Free Grammar (CFG) dengan setiap produksinya berbentuk :
A → BC atau A → a.
Transformasi CFG ke CNF adalah transformasi berikut :
Aturan produksi dalam bentuk normal Chomsky ruas kanannya tepat berupa sebuah terminal atau dua variabel.
Misalkan:
Langkah-langkah pembentukan bentuk normal Chomsky secara umum sebagai berikut:
Bisa dilihat tahapan-tahapan tersebut pada gambar berikut:
Contoh, Context Free Grammar ( kita anggap CFG pada bab ini sudah mengalami Penyederhanaan CFG ):
S → bA | aB
A → bAA | aS | a
B → aBB | bS | b
Aturan produksi yang sudah dalam bentuk normal Chomsky:
A → a
B → b
Dilakukan penggantian aturan produksi yang belum bentuk normal Chomsky (‘=>’ bisa dibaca berubah menjadi):
S → bA => S → P1A
S → aB => S → P2B
A → bAA =>A → P1AA => A → P1P3
A → aS => A → P2S
B → aBB => B → P2BB => B → P2P4
B → bS => B → P1S
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 → P2P4
B → P1S
P1 → b
P2 → a
P3 → AA
P4 → BB
P1 = P, P2 =Q, P3 =R, P4 =T, sehingga aturan produksinya menjadi:
S → PA
S → QB
A → PR
A → QS
A → a
B → QT
B → PS
B → b
P → b
Q → a
R → AA
T → BB
Source : https://kelasqta.files.wordpress.com/2013/01/chapter-12-tbo.pdf
Universitas Budi Luhur – Jakarta
https://www.budiluhur.ac.id/