Chomsky Normal Form

CFG อยู่ใน Chomsky Normal Form หากโปรดักชั่นอยู่ในรูปแบบต่อไปนี้ -

• ก→ก
• ก→ พ.ศ.
• S →ε

โดยที่ A, B และ C ไม่ใช่ขั้วและ a คือเทอร์มินัล

อัลกอริทึมเพื่อแปลงเป็น Chomsky Normal Form -

Step 1 - หากสัญลักษณ์เริ่มต้น S เกิดขึ้นทางด้านขวาสร้างสัญลักษณ์เริ่มต้นใหม่ S’ และการผลิตใหม่ S’→ S.

Step 2- ลบการผลิตที่เป็นโมฆะ (โดยใช้อัลกอริทึมการลบการผลิตที่เป็นโมฆะที่กล่าวถึงก่อนหน้านี้)

Step 3- ลบการผลิตหน่วย (โดยใช้อัลกอริทึมการกำจัดการผลิตหน่วยที่กล่าวถึงก่อนหน้านี้)

Step 4 - เปลี่ยนการผลิตแต่ละครั้ง A → B₁…B_n ที่ไหน n > 2 ด้วย A → B₁C ที่ไหน C → B₂ …B_n. ทำซ้ำขั้นตอนนี้สำหรับการผลิตทั้งหมดที่มีสัญลักษณ์สองตัวขึ้นไปทางด้านขวา

Step 5 - หากด้านขวาของการผลิตใด ๆ อยู่ในรูปแบบ A → aB โดยที่ a คือเทอร์มินัลและ A, B ไม่ใช่ขั้วจากนั้นการผลิตจะถูกแทนที่ด้วย A → XB และ X → a. ทำซ้ำขั้นตอนนี้สำหรับทุกการผลิตที่อยู่ในรูปแบบA → aB.

ปัญหา

แปลง CFG ต่อไปนี้เป็น CNF

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

วิธีการแก้

(1) ตั้งแต่ S ปรากฏใน RHS เราเพิ่มสถานะใหม่ S₀ และ S₀→S ถูกเพิ่มลงในชุดการผลิตและกลายเป็น -

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

(2) ตอนนี้เราจะลบโปรดักชั่นว่าง -

B →∈และ A →∈

หลังจากลบ B →εชุดการผลิตจะกลายเป็น -

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

หลังจากลบ A →∈ชุดการผลิตจะกลายเป็น -

S ₀ → S, S → ASA | aB | ก | AS | SA | S, A → B | S, B →ข

(3) ตอนนี้เราจะลบการผลิตหน่วย

หลังจากลบ S → S ชุดการผลิตจะกลายเป็น -

S ₀ → S, S → ASA | aB | ก | AS | SA, A → B | S, B →ข

หลังจากลบ S ₀ → S ชุดการผลิตจะกลายเป็น -

ส₀ → ASA | aB | ก | AS | SA, S → ASA | aB | ก | AS | ส

A → B | S, B →ข

หลังจากลบ A → B ชุดการผลิตจะกลายเป็น -

ส₀ → ASA | aB | ก | AS | SA, S → ASA | aB | ก | AS | ส

A → S | ข

B →ข

หลังจากลบ A → S ชุดการผลิตจะกลายเป็น -

ส₀ → ASA | aB | ก | AS | SA, S → ASA | aB | ก | AS | ส

A → b | ASA | aB | ก | AS | SA, B →ข

(4) ตอนนี้เราจะพบมากกว่าสองตัวแปรใน RHS

ที่นี่ S ₀ → ASA, S → ASA, A → ASA ละเมิดสองขั้วที่ไม่ใช่ใน RHS

ดังนั้นเราจะใช้ขั้นตอนที่ 4 และขั้นตอนที่ 5 เพื่อรับชุดการผลิตขั้นสุดท้ายต่อไปนี้ซึ่งอยู่ใน CNF -

S ₀ → AX | aB | ก | AS | ส

S → AX | aB | ก | AS | ส

A → b | AX | aB | ก | AS | ส

B →ข

X → SA

(5)เราต้องเปลี่ยนโปรดักชั่น S ₀ → aB, S → aB, A → aB

และชุดการผลิตขั้นสุดท้ายจะกลายเป็น -

S ₀ → AX | YB | ก | AS | ส

S → AX | YB | ก | AS | ส

A → b A → b | AX | YB | ก | AS | ส

B →ข

X → SA

Y →ก