Konversi CNF

Back to IF2224 Teori Bahasa Formal dan Otomata

Topic: Chomsky Normal Form (CNF) & Konversi

Questions/Cues

• Definisi Formal CNF

• Motivasi CNF

• Syarat Produksi

• Langkah 1: Clean Up

• Langkah 2: Terminal

• Langkah 3: Cascade

Reference Points

• Slide 15_2025: Hal 3 - 15

1. Definisi Chomsky Normal Form (CNF)

Sebuah Tata Bahasa Bebas Konteks (CFG) berada dalam bentuk CNF jika dan hanya jika setiap aturan produksi memenuhi salah satu dari dua format berikut:

1. $A\to BC$: Variabel menurunkan tepat dua variabel.

2. $A\to a$: Variabel menurunkan tepat satu terminal.

Segala bentuk produksi lain seperti produksi kosong ($ϵ$), produksi unit ($A\to B$), atau campuran terminal-variabel di sisi kanan dilarang.

2. Langkah-Langkah Konversi CFG ke CNF

Proses konversi dilakukan melalui tiga tahapan utama secara berurutan:

Langkah 1: Pembersihan Grammar (Clean Up)

Sebelum konversi, grammar harus dibersihkan dari tiga masalah:

• Eliminasi Useless Symbols: Menghapus simbol yang tidak bisa menghasilkan terminal string (non-generating) atau tidak bisa dicapai dari start symbol (non-reachable).

• Eliminasi $ϵ$-productions: Menghapus $A\to ϵ$ dengan menduplikasi aturan produksi yang mengandung variabel nullable tersebut.

• Eliminasi Unit Productions: Menghapus $A\to B$ dengan menggantinya dengan semua produksi non-unit yang dimiliki oleh $B$.

Langkah 2: Pemisahan Terminal dalam Produksi Panjang

Masalah: Produksi dengan panjang $\ge 2$ yang mengandung terminal (contoh: $A\to aB$).

• Prosedur: Untuk setiap terminal $a$ dalam body produksi panjang, buat variabel baru $X_a$. Ganti $a$ dengan $X_a$ dan tambahkan aturan $X_a\to a$.

Langkah 3: Pemecahan Body Panjang (Cascade) Masalah: Produksi dengan jumlah variabel di sisi kanan $\ge 3$ (contoh: $A\to B_1{B}_2{B}_3$).

• Prosedur: Pecah menjadi rangkaian produksi biner menggunakan variabel pembantu.

• Misal $A\to B_1{B}_2{B}_3$ diubah menjadi:

1. $A\to B_1{C}_1$

2. $C_1\to B_2{B}_3$

3. Karakteristik Parse Tree CNF

Dalam format CNF, setiap parse tree akan memiliki struktur pohon biner. Jika string memiliki panjang $n$, maka pohon penurunan tersebut akan memiliki tepat $2n-1$ node internal. Struktur yang seragam ini memungkinkan implementasi algoritma parsing yang lebih efisien.

Summary

Chomsky Normal Form (CNF) adalah bentuk standar CFG yang hanya mengizinkan produksi $A\to BC$ atau $A\to a$. Proses konversi melibatkan pembersihan grammar (hapus $ϵ$, unit, dan useless symbols), pemisahan terminal menggunakan variabel baru pada produksi panjang, serta pemecahan variabel jamak menjadi struktur kaskade biner. Standarisasi ini sangat penting untuk efisiensi algoritma parsing seperti CYK.

Additional Information

Detail Teknis: Kompleksitas Konversi

Konversi dari CFG ke CNF secara teoretis dapat menyebabkan pertumbuhan jumlah produksi secara eksponensial jika dilakukan secara naif (terutama pada eliminasi $ϵ$). Namun, dengan optimasi (memecah body sebelum eliminasi nullable), pertumbuhan ini dapat ditekan menjadi polinomial ($O(n^2)$ terhadap ukuran grammar asli).

Alasan Matematis Pembatasan Biner

Pembatasan menjadi tepat dua variabel ($A\to BC$) bertujuan untuk membatasi ruang pencarian saat melakukan parsing. Dengan struktur biner, algoritma dapat menggunakan teknik divide and conquer yang sistematis untuk mengecek setiap kemungkinan titik pemisahan (split point) pada string input.

Sumber & Referensi Lanjutan:

• Slide 15_2025 CNF & CFL Properties (Hal 3-15).

• Hopcroft, Motwani, & Ullman: Introduction to Automata Theory, Languages, and Computation.

Spaced Repetition Questions (Review)

1. Apa syarat produksi variabel dalam CNF?

Sisi kanan produksi harus terdiri dari tepat dua buah variabel (tidak boleh terminal atau campuran).

2. Mengapa produksi $A \rightarrow aB$ tidak diperbolehkan dalam CNF?

Karena melanggar syarat bentuk normal; produksi yang mengandung terminal di sisi kanan hanya boleh berisi tepat satu terminal saja ($A \rightarrow a$).

3. Sebutkan urutan eliminasi yang harus dilakukan pada tahap "Clean Up"!

Eliminasi $\epsilon$-productions, eliminasi unit productions, lalu eliminasi useless symbols.

4. Bagaimana cara memecah produksi $A \rightarrow BCD$ menjadi format CNF?

Membuat kaskade: $A \rightarrow B C_1$ dan $C_1 \rightarrow CD$, di mana $C_1$ adalah variabel baru.

5. Berapa jumlah node internal pada parse tree CNF untuk string sepanjang $n=5$?

Menggunakan rumus $2n-1$, maka $2(5)-1 = 9$ node internal.