สูบเลมมาเพื่อ CFG

เลมมา

ถ้า L เป็นภาษาที่ไม่มีบริบทมีความยาวในการปั๊ม p เช่นนั้นสตริงใด ๆ w ∈ L ความยาว ≥ p สามารถเขียนเป็น w = uvxyz, ที่ไหน vy ≠ ε, |vxy| ≤ pและสำหรับทุกคน i ≥ 0, uvⁱxyⁱz ∈ L.

การใช้งานของการสูบเล็มมา

คำศัพท์การปั๊มใช้เพื่อตรวจสอบว่าไวยากรณ์ไม่มีบริบทหรือไม่ ให้เราดูตัวอย่างและแสดงวิธีการตรวจสอบ

ปัญหา

ค้นหาว่าภาษา L = {xⁿyⁿzⁿ | n ≥ 1} ไม่มีบริบทหรือไม่

วิธีการแก้

ปล่อย Lไม่มีบริบท จากนั้นL ต้องเป็นไปตามคำอธิบายการสูบน้ำ

ตอนแรกให้เลือกหมายเลข nของ lemma ปั๊ม จากนั้นใช้ Z เป็น 0 ⁿ 1 ⁿ 2 n

หยุดพัก z เป็น uvwxy, ที่ไหน

|vwx| ≤ n and vx ≠ ε.

ดังนั้น vwxไม่สามารถเกี่ยวข้องกับทั้ง 0 และ 2 เนื่องจาก 0 สุดท้ายและ 2 แรกอยู่ห่างกันอย่างน้อย (n + 1) ตำแหน่ง มีสองกรณี -

Case 1 - vwxไม่มี 2 วินาที แล้วvxมีเพียง 0s และ 1s แล้วuwyซึ่งจะต้องอยู่ใน L, มี n 2 วินาที แต่น้อยกว่า n 0 วินาทีหรือ 1 วินาที

Case 2 - vwx ไม่มี 0

ความขัดแย้งเกิดขึ้นที่นี่

ดังนั้น L ไม่ใช่ภาษาที่ไม่มีบริบท