BENTUK NORMAL CHOMSKY

BENTUK NORMAL CHOMSKY

Bentuk normal Chomsky / Chomsky Normal Form (CNF) merupakan salah satu bentuk normal yang sangat berguna untuk tata bahasa bebas konteks.

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 konteks tersebut:

1.         Tidak memiliki produksi useless

2.         Tidak memiliki produksi unit

3.         Tidak memiliki produksi ε

Aturan produksi dalam bentuk normal Chomsky ruas kanannya tepat berupa sebuah terminal atau dua variabel.

Misalkan:

A -> BC

A -> b

B -> a

C -> BA | d

Pembentukan Bentuk Normal Chomsky  

Langkah-langkah pembentukan  bentuk normal Chomsky  secara umum sebagai berikut:

1.   Biarkan aturan produksi yang sudah dalam  bentuk normal Chomsky

2.   Lakukan penggantian aturan produksi yang ruas kanannya memuat simbol terminal

      dan panjang ruas kanan > 1

3    Lakukan penggantian aturan produksi yang ruas kanannya memuat > 2 simbol

      variabel Non Terminal

4    Penggantian-penggantian tersebut bisa dilakukan berkali-kali sampai akhirnya

      semua aturan produksi dalam  bentuk normal Chomsky

5    Selama dilakukan penggantian, kemungkinan kita akan memperoleh aturan-aturan

      produksi baru, dan juga memunculkan simbol-simbol variabel baru

Contoh, tata bahasa bebas konteks ( kita anggap tata bahasa bebas konteks pada bab ini sudah mengalami penyederhanaan ):

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 àP₁A

S -> aB => S à P₁B

A -> bAA => S à P₁AA => A à P₁P₃
A -> aS => A à P₂S

B -> aBB => B à P₂BB => B à P₂P₄
B -> bS => B à P₁S

Terbentuk aturan produksi dan simbol variabel baru:

P₁ -> b

P₂ -> a

P₃ -> AA
           P₄ -> BB

Hasil akhir aturan produksi dalam bentuk normal Chomsky :

 A -> a
            B -> b

            S -> P₁A
            S -> P₂B
            A -> P₁P₃

            A -> P₂S
            B -> P₂P₄

            B -> P₁S
            P₁ -> b
            P₂ -> a

            P₃ -> AA
            P₄ -> BB