Vclass

Nama

: Yudya Rahman

Npm

: 50405773

Kelas

: 3 IA 14

Bentuk normal Chomsky / Chomsky Normal Form (CNF) merupakan salah satu bentuk normal yang sangat berguna untuk tata bahasa bebas konteks (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: • Tidak memiliki produksi useless • Tidak memiliki produksi unit • Tidak memiliki produksi ε Aturan produksi dalam bentuk normal Chomsky ruas kanannya tepat berupa sebuah terminal atau dua variabel. Pembentukan Bentuk Normal Chomsky Langkah-langkah pembentukan bentuk normal Chomsky secara umum sebagai berikut: • Biarkan aturan produksi yang sudah dalam bentuk normal Chomsky • Lakukan penggantian aturan produksi yang ruas kanannya memuat simbol terminal dan panjang ruas kanan > 1 • Lakukan penggantian aturan produksi yang ruas kanannya memuat > 2 simbol variabel • Penggantian-penggantian tersebut bisa dilakukan berkali-kali sampai akhirnya semua aturan produksi dalam bentuk normal Chomsky

• Selama dilakukan penggantian, kemungkinan kita akan memperoleh aturan-aturan produksi baru, dan juga memunculkan simbol-simbol variabel baru Soal : Transformasikan tata bahasa bebas contex ke dalam bentuk normal Chomsky : a. S  aSb | ab b. S  aSaA | A A  abA | b Jawab : Algoritma pembentukannya adalah : 1. Biarkan aturan produksi yang sudah dalam bentuk BNC 2. Lakukan pergantian aturan produksi yang ruas kanannya memuat simbol terminal & panjang ruas kanan > 1 3. Lakukan penggantian aturan produksi yang ruas kanannyamemuat > 2 simbol variabel 4. Penggantian‐penggantian tersebut bisa dilakukan berkali‐kali sampai akhirnya semua aturan produksi berkali dalam bentuk BNC 5. Selama dilakukan penggantian, kemungkinan kita akan l h d k i b d i b l memperoleh aturan‐aturan produksi baru, dan simbol variabel baru a. Dilakukan penggantian peraturan produksi yang sudah dalam bentuk normal Chomsky (‘=>’ bisa di baca berubah menjadi) : S  aSb | ab S  aSb => S  P1SP2 S  ab => S  P1P2 Maka terbentuk aturan produksi dan symbol variable baru : P1  a P2  b

Maka hasil akhir aturan produksi dalam bentuk normal Chomsky adalah : S  aSb => S  P1SP2 S  ab => S  P1P2 P1  a P2  b b. Dilakukan penggantian peraturan produksi yang sudah dalam bentuk normal Chomsky (‘=>’ bisa di baca berubah menjadi) : S  aSaA | A A  abA | b S  aSaA => S  P1SP1A SA A  abA => A  P1P2A A  b => A  P2 Maka terbentuk aturan produksi dan simbol variabel baru : P1  a P2  b Maka hasil akhir aturan produksi dalam bentuk normal Chomsky adalah : S  P1SP1A SA A  P1P2A A  P2 P1  a P2  b