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 → B1…Bn dimana n > 2 dengan A → B1C dimana C → B2 …Bn. 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 S0 dan S0→S ditambahkan ke set produksi dan menjadi -

S 0 → 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 0 → S, S → ASA | aB | a, A → B | S | ∈, B → b

Setelah membuang A → ∈, set produksi menjadi -

S 0 → 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 0 → S, S → ASA | aB | a | SEBAGAI | SA, A → B | S, B → b

Setelah melepas S 0 → S, set produksi menjadi -

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

A → B | S, B → b

Setelah membuang A → B, set produksi menjadi -

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

A → S | b

B → b

Setelah melepas A → S, set produksi menjadi -

S 0 → 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 0 → 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 0 → 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 0 → aB, S → aB, A → aB

Dan set produksi akhir menjadi -

S 0 → 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