รูปแบบปกติของ Greibach

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

ก→ข

A → bD 1 … D n

S →ε

โดยที่ A, D 1 , .... , D nไม่ใช่เทอร์มินัลและ b คือเทอร์มินัล

อัลกอริทึมในการแปลง CFG เป็น Greibach Normal Form

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

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

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

Step 4 - ลบการเรียกซ้ำซ้ายทั้งทางตรงและทางอ้อมทั้งหมด

Step 5 - ทำการทดแทนการผลิตที่เหมาะสมเพื่อแปลงเป็นรูปแบบ GNF ที่เหมาะสม

ปัญหา

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

S → XY | Xn | น

X → mX | ม

Y → Xn | o

วิธีการแก้

ที่นี่ Sไม่ปรากฏทางด้านขวาของการผลิตใด ๆ และไม่มีหน่วยหรือการผลิตที่เป็นโมฆะในชุดกฎการผลิต ดังนั้นเราสามารถข้ามขั้นตอนที่ 1 ไปยังขั้นตอนที่ 3 ได้

Step 4

ตอนนี้หลังจากเปลี่ยน

X ใน S → XY | Xo | น

ด้วย

mX | ม

เราได้รับ

S → mXY | mY | mXo | mo | น.

และหลังจากเปลี่ยน

X ใน Y → X n | o

ด้วยด้านขวาของ

X → mX | ม

เราได้รับ

Y → mXn | mn | o.

เพิ่มโปรดักชั่นใหม่สองรายการ O → o และ P → p ในชุดการผลิตจากนั้นเราก็มาถึง GNF สุดท้ายดังต่อไปนี้ -

S → mXY | mY | mXC | mC | น

X → mX | ม

Y → mXD | mD | o

O → o

P →หน้า