PDA และไวยากรณ์ที่ไม่มีบริบท
ถ้าเป็นไวยากรณ์ G ไม่มีบริบทเราสามารถสร้าง PDA แบบไม่กำหนดเงื่อนไขเทียบเท่าซึ่งยอมรับภาษาที่สร้างขึ้นโดยไวยากรณ์ที่ไม่มีบริบท G. ตัวแยกวิเคราะห์สามารถสร้างขึ้นสำหรับไวยากรณ์G.
นอกจากนี้ถ้า P เป็นระบบอัตโนมัติแบบเลื่อนลงซึ่งสามารถสร้างไวยากรณ์ G ที่ไม่มีบริบทเทียบเท่าได้โดยที่
L(G) = L(P)
ในสองหัวข้อถัดไปเราจะพูดถึงวิธีการแปลงจาก PDA เป็น CFG และในทางกลับกัน
อัลกอริทึมเพื่อค้นหา PDA ที่สอดคล้องกับ CFG ที่กำหนด
Input - CFG, G = (V, T, P, S)
Output- PDA เทียบเท่า, P = (Q, ∑, S, δ, q 0 , I, F)
Step 1 - แปลงการผลิตของ CFG เป็น GNF
Step 2 - PDA จะมีเพียงสถานะเดียว {q}
Step 3 - สัญลักษณ์เริ่มต้นของ CFG จะเป็นสัญลักษณ์เริ่มต้นใน PDA
Step 4 - ทั้งหมดที่ไม่ใช่ขั้วของ CFG จะเป็นสัญลักษณ์สแต็กของ PDA และขั้วทั้งหมดของ CFG จะเป็นสัญลักษณ์อินพุตของ PDA
Step 5 - สำหรับการผลิตในแต่ละรูปแบบ A → aX โดยที่ a คือเทอร์มินัลและ A, X เป็นการรวมกันของเทอร์มินัลและไม่ใช่เทอร์มินัลทำการเปลี่ยน δ (q, a, A).
ปัญหา
สร้าง PDA จาก CFG ต่อไปนี้
G = ({S, X}, {a, b}, P, S)
โปรดักชั่นอยู่ที่ไหน -
S → XS | ε , A → aXb | Ab | ab
วิธีการแก้
ให้ PDA เทียบเท่า
P = ({q}, {a, b}, {a, b, X, S}, δ, q, S)
ที่ไหนδ -
δ (q, ε, S) = {(q, XS), (q, ε)}
δ (q, ε, X) = {(q, aXb), (q, Xb), (q, ab)}
δ (q, a, a) = {(q, ε)}
δ (q, 1, 1) = {(q, ε)}
อัลกอริทึมเพื่อค้นหา CFG ที่สอดคล้องกับ PDA ที่กำหนด
Input - CFG, G = (V, T, P, S)
Output- PDA เทียบเท่า, P = (Q, ∑, S, δ, q 0 , I, F) ดังนั้นส่วนที่ไม่ใช่ขั้วของไวยากรณ์ G จะเป็น {X wx | W, x ∈ Q} และรัฐเริ่มต้นจะเป็นQ0, F
Step 1- สำหรับทุก w, x, y, z ∈ Q, m ∈ S และ a, b ∈ ∑ ถ้าδ (w, a, ε) มี (y, m) และ (z, b, m) ประกอบด้วย (x, ε) เพิ่มกฎการผลิต X wx → a X yz b ในไวยากรณ์ G
Step 2- สำหรับทุก ๆ w, x, y, z ∈ Q ให้เพิ่มกฎการผลิต X wx → X wy X yxในไวยากรณ์ G
Step 3- สำหรับ w ∈ Q ให้เพิ่มกฎการผลิต X ww →εในไวยากรณ์ G