การลดความซับซ้อนของ CFG

ใน CFG อาจเกิดขึ้นได้ว่าไม่จำเป็นต้องใช้กฎและสัญลักษณ์ในการผลิตทั้งหมดสำหรับการสร้างสตริง นอกจากนี้อาจมีการผลิตที่เป็นโมฆะและการผลิตต่อหน่วย เรียกว่าการกำจัดการผลิตและสัญลักษณ์เหล่านี้simplification of CFGs. การทำให้เข้าใจง่ายประกอบด้วยขั้นตอนต่อไปนี้ -

  • การลด CFG
  • การกำจัดยูนิตโปรดักชั่น
  • การกำจัด Null Productions

การลด CFG

CFG จะลดลงในสองขั้นตอน -

Phase 1 - ที่มาของไวยากรณ์เทียบเท่า G’จาก CFG Gเพื่อให้แต่ละตัวแปรได้รับสตริงเทอร์มินัล

Derivation Procedure -

ขั้นตอนที่ 1 - รวมสัญลักษณ์ทั้งหมด W1ซึ่งได้รับบางเทอร์มินัลและเริ่มต้น i=1.

ขั้นตอนที่ 2 - รวมสัญลักษณ์ทั้งหมด Wi+1ที่ได้มา Wi.

ขั้นตอนที่ 3 - เพิ่มขึ้น i และทำซ้ำขั้นตอนที่ 2 จนถึง Wi+1 = Wi.

ขั้นตอนที่ 4 - รวมกฎการผลิตทั้งหมดที่มี Wi ในนั้น.

Phase 2 - ที่มาของไวยากรณ์เทียบเท่า G”จาก CFG G’ดังนั้นสัญลักษณ์แต่ละตัวจะปรากฏในรูปแบบความรู้สึก

Derivation Procedure -

ขั้นตอนที่ 1 - ใส่สัญลักษณ์เริ่มต้นใน Y1 และเริ่มต้น i = 1.

ขั้นตอนที่ 2 - รวมสัญลักษณ์ทั้งหมด Yi+1ที่ได้มาจาก Yi และรวมกฎการผลิตทั้งหมดที่นำไปใช้

ขั้นตอนที่ 3 - เพิ่มขึ้น i และทำซ้ำขั้นตอนที่ 2 จนถึง Yi+1 = Yi.

ปัญหา

ค้นหาไวยากรณ์ที่ลดลงเทียบเท่ากับไวยากรณ์ G โดยมีกฎการผลิต P: S → AC | B, A → a, C → c | BC, E → aA | จ

วิธีการแก้

Phase 1 -

T = {a, c, e}

W 1 = {A, C, E} จากกฎ A → a, C → c และ E → aA

W 2 = {A, C, E} U {S} จากกฎ S → AC

3 = {A, C, E, S} U ∅

ตั้งแต่ W 2 = W 3เราสามารถได้รับ G 'เป็น -

G '= {{A, C, E, S}, {a, c, e}, P, {S}}

โดยที่ P: S → AC, A → a, C → c, E → aA | จ

Phase 2 -

Y 1 = {S}

Y 2 = {S, A, C} จากกฎ S → AC

Y 3 = {S, A, C, a, c} จากกฎ A → a และ C → c

Y 4 = {S, A, C, a, c}

ตั้งแต่ Y 3 = Y 4เราสามารถหาค่า G "เป็น -

G” = {{A, C, S}, {a, c}, P, {S}}

โดยที่ P: S → AC, A → a, C → c

การกำจัดยูนิตโปรดักชั่น

กฎการผลิตใด ๆ ในรูปแบบ A → B ที่เรียกว่า A, B ∈ Non-terminal unit production..

ขั้นตอนการกำจัด -

Step 1 - ในการลบ A → Bเพิ่มการผลิต A → x กฎไวยากรณ์เมื่อใดก็ตาม B → xเกิดขึ้นในไวยากรณ์ [x ∈ Terminal, x สามารถเป็น Null]

Step 2 - ลบ A → B จากไวยากรณ์

Step 3 - ทำซ้ำตั้งแต่ขั้นตอนที่ 1 จนกว่าการผลิตหน่วยทั้งหมดจะถูกลบออก

Problem

ลบการผลิตยูนิตออกจากรายการต่อไปนี้ -

S → XY, X → a, Y → Z | b, Z → M, M → N, N →ก

Solution -

มีการผลิต 3 หน่วยในไวยากรณ์ -

Y → Z, Z → M และ M → N

At first, we will remove M → N.

ในฐานะที่เป็น N → a เราเพิ่ม M → a และ M → N จะถูกลบออก

ชุดการผลิตจะกลายเป็น

S → XY, X → a, Y → Z | b, Z → M, M → a, N →ก

Now we will remove Z → M.

ในฐานะ M → a เราเพิ่ม Z → a และ Z → M จะถูกลบออก

ชุดการผลิตจะกลายเป็น

S → XY, X → a, Y → Z | b, Z → a, M → a, N →ก

Now we will remove Y → Z.

ในฐานะ Z → a เราเพิ่ม Y → a และ Y → Z จะถูกลบออก

ชุดการผลิตจะกลายเป็น

S → XY, X → a, Y → a | b, Z → a, M → a, N →ก

ตอนนี้ Z, M และ N ไม่สามารถเข้าถึงได้ดังนั้นเราจึงสามารถลบสิ่งเหล่านั้นได้

CFG ขั้นสุดท้ายไม่มีการผลิตต่อหน่วย -

S → XY, X → a, Y → a | ข

การกำจัด Null Productions

ใน CFG สัญลักษณ์ที่ไม่ใช่ขั้ว ‘A’ เป็นตัวแปรที่เป็นโมฆะหากมีการผลิต A → ε หรือมีที่มาที่เริ่มต้นที่ A และสุดท้ายลงเอยด้วย

ε: ก→ ....... …→ε

ขั้นตอนการกำจัด

Step 1 - ค้นหาตัวแปรที่ไม่ใช่ขั้วที่เป็นโมฆะซึ่งได้รับε

Step 2 - สำหรับการผลิตแต่ละครั้ง A → aสร้างโปรดักชั่นทั้งหมด A → x ที่ไหน x ได้มาจาก ‘a’ โดยการถอดขั้วที่ไม่ใช่หนึ่งหรือหลายขั้วออกจากขั้นตอนที่ 1

Step 3 - รวมการผลิตดั้งเดิมกับผลลัพธ์ของขั้นตอนที่ 2 และนำออก ε - productions.

Problem

ลบการผลิตว่างจากสิ่งต่อไปนี้ -

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

Solution -

มีสองตัวแปรที่เป็นโมฆะ - A และ B

At first, we will remove B → ε.

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

S → ASA | aB | b | ก, กεข | b | & epsilon, B → b

Now we will remove A → ε.

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

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

นี่คือชุดการผลิตขั้นสุดท้ายที่ไม่มีการเปลี่ยนค่าว่าง