Bentuk Normal Chomsky

CFG dalam Bentuk Normal Chomsky jika Produksi dalam bentuk berikut -

• A → a
• A → BC
• S → ε

di mana A, B, dan C adalah non-terminal dan a adalah terminal.

Algoritma untuk Mengubah ke Bentuk Normal Chomsky -

Step 1 - Jika simbol start S terjadi di beberapa sisi kanan, buat simbol awal baru S’ dan produksi baru S’→ S.

Step 2- Hapus produksi Null. (Menggunakan algoritma penghapusan produksi Null yang dibahas sebelumnya)

Step 3- Hapus produksi unit. (Menggunakan algoritma penghilangan produksi Unit yang dibahas sebelumnya)

Step 4 - Ganti setiap produksi A → B₁…B_n dimana n > 2 dengan A → B₁C dimana C → B₂ …B_n. Ulangi langkah ini untuk semua produksi yang memiliki dua atau lebih simbol di sisi kanan.

Step 5 - Jika sisi kanan produksi ada dalam bentuk A → aB dimana a adalah terminal dan A, B bersifat non-terminal, maka produksi digantikan oleh A → XB dan X → a. Ulangi langkah ini untuk setiap produksi yang ada dalam bentukA → aB.

Masalah

Ubah CFG berikut menjadi CNF

S → ASA | aB, A → B | S, B → b | ε

Larutan

(1) Sejak S muncul di kanan, kami menambahkan status baru S₀ dan S₀→S ditambahkan ke set produksi dan menjadi -

S ₀ → S, S → ASA | aB, A → B | S, B → b | ∈

(2) Sekarang kita akan menghapus produksi nol -

B → ∈ dan A → ∈

Setelah membuang B → ε, set produksi menjadi -

S ₀ → S, S → ASA | aB | a, A → B | S | ∈, B → b

Setelah membuang A → ∈, set produksi menjadi -

S ₀ → S, S → ASA | aB | a | SEBAGAI | SA | S, A → B | S, B → b

(3) Sekarang kami akan menghapus produksi unit.

Setelah melepas S → S, set produksi menjadi -

S ₀ → S, S → ASA | aB | a | SEBAGAI | SA, A → B | S, B → b

Setelah melepas S ₀ → S, set produksi menjadi -

S ₀ → ASA | aB | a | SEBAGAI | SA, S → ASA | aB | a | SEBAGAI | SA

A → B | S, B → b

Setelah membuang A → B, set produksi menjadi -

S ₀ → ASA | aB | a | SEBAGAI | SA, S → ASA | aB | a | SEBAGAI | SA

A → S | b

B → b

Setelah melepas A → S, set produksi menjadi -

S ₀ → ASA | aB | a | SEBAGAI | SA, S → ASA | aB | a | SEBAGAI | SA

A → b | ASA | aB | a | SEBAGAI | SA, B → b

(4) Sekarang kita akan menemukan lebih dari dua variabel di RHS

Di sini, S ₀ → ASA, S → ASA, A → ASA melanggar dua Non-terminal di RHS

Karenanya kami akan menerapkan langkah 4 dan langkah 5 untuk mendapatkan set produksi akhir berikut yang ada di CNF -

S ₀ → AX | aB | a | SEBAGAI | SA

S → AX | aB | a | SEBAGAI | SA

A → b | AX | aB | a | SEBAGAI | SA

B → b

X → SA

(5)Kita harus mengubah produksi S ₀ → aB, S → aB, A → aB

Dan set produksi akhir menjadi -

S ₀ → AX | YB | a | SEBAGAI | SA

S → AX | YB | a | SEBAGAI | SA

A → b A → b | AX | YB | a | SEBAGAI | SA

B → b

X → SA

Y → a