การใช้ CFL Pumping Lemma อย่างถูกต้อง

Aug 16 2020

ฉันเจอคำถามนี้เกี่ยวกับการแสดงภาษานั้น $L = \{w \epsilon \{a, b, c\}^*: n_a(w) + n_b(w) = n_c(w)\}$ไม่มีบริบท แต่ไม่เป็นเชิงเส้นในหนังสือของ Peter Linz นั่นทำได้อย่างง่ายดายโดยคำขยายการปั๊มแยกต่างหากสำหรับภาษาเชิงเส้น (ตามที่ระบุในหนังสือของ Linz) แต่คำถามของฉันแตกต่างออกไป

เห็นได้ชัดว่านี่คือ CFL และสามารถสร้างหุ่นยนต์แบบเลื่อนลงได้ แต่ถ้าฉันใช้คำขยายการปั๊มสำหรับ CFL ฉันพบว่าฉันสามารถปั๊มสตริงที่ไม่ได้เป็นของภาษาซึ่งหมายความว่าภาษานั้นไม่ใช่ CFL เห็นได้ชัดว่าฉันทำอะไรผิด

ไปตามรูปแบบ "เหมือนเกม" ที่กำหนดในลินซ์บอกว่าคุณเลือก $w = a^mb^mc^{2m}$, $|w| \ge m$. ฝ่ายตรงข้ามสามารถเลือกการสลายตัวได้หลายแบบ$w = uvxyz$สามารถมีลักษณะดังนี้ -:

  • $v = a^k, y = a^l$: กรณีที่ $|vxy|$ มีอยู่ในไฟล์ $a$ของสตริง ปั๊ม$i = 0$และจากนั้น $w_0 = a^{m – (k + l)}b^mc^{2m}$ ไม่สามารถเป็นภาษาได้เนื่องจากไม่มีความเท่าเทียมกันอีกต่อไป
  • $v = a^k, y = b^l$: กรณีที่ $v$ อยู่ใน $a$ มาตรา, $x$ ครอบคลุมทั่วทั้ง $a$และ $b$และ $y$ อยู่ใน $b$มาตรา. อีกครั้งปั๊ม$i = 0$. $w_0 = a^{m – k}b^{m – l}c^{2m}$ ไม่สามารถเป็นภาษา

มีกรณีเช่นนี้มากขึ้น ฉันผิดพลาดตรงไหนในการสมัคร CFL PL?

คำตอบ

1 vonbrand Aug 17 2020 at 08:20

คำขยายการสูบน้ำสำหรับ CFL ระบุว่าถ้า $L$ เป็น CFL มีค่าคงที่ $N \ge 1$ เช่นนั้นสำหรับทุกคน $\omega \in L$ ด้วย $\lvert \omega \rvert \ge N$ มีการแบ่ง $\sigma = u v w x y$ ด้วย $\lvert v w x \rvert \le N$ และ $v x \ne \varepsilon$ ดังนั้น $u v^k w x^k y \in L$ เพื่อทุกสิ่ง $k \ge 0$.

(คำขยายสำหรับภาษาปกติจะคล้ายกันการสนทนาด้านล่างใช้กับการเปลี่ยนแปลงเล็กน้อย)

คุณต้องการพิสูจน์ด้วยความขัดแย้งว่า $L$ไม่ใช่ CFL ดังนั้นคุณถือว่า$L$เป็น CFL และมีความขัดแย้งกับคำหลัก ซึ่งหมายความว่าโดยละเอียด:

  • เช่น $L$เป็น CFL มันเป็นไปตามคำย่อ โดยเฉพาะอย่างยิ่งมีค่าคงที่$N$ ดังนั้น...
  • ในฐานะที่เป็น lemma ระบุสตริงยาวทั้งหมดใน$L$ สามารถแบ่งออกได้คุณมีอิสระที่จะเลือกหนึ่งที่ใช้งานง่าย
  • ศัพท์บัญญัติมีบางส่วนของ$\omega$เช่นนั้น .... สำหรับทุกคน $k \ge 0$... ; คุณต้องพิสูจน์ว่าไม่มีการแบ่งงานใด ๆ ในทางปฏิบัติคุณแบ่งส่วน$\omega$( กองใดก็ได้ ) และเลือกบางส่วน$k$สำหรับมันที่ไม่มีสตริงในภาษา คุณอาจต้องแบ่งเป็นกรณี ๆ ไป

จะเกิดอะไรขึ้นสำหรับสตริงที่ไม่ได้เป็นของภาษาหรือสั้นกว่า $N$ไม่เกี่ยวข้องโดยสิ้นเชิง อาจเป็นไปได้ว่าสตริงบางตัวสามารถสูบได้ซึ่งค่าบางค่าของ$k$ใช้ได้กับทุกสตริง ... สิ่งที่สำคัญคือสำหรับสตริงเดียว$\omega$(ค่าที่คุณเลือก) ไม่มีการหารใดที่ใช้ได้กับค่าเดียว$k$(อีกครั้งหนึ่งที่คุณเลือก) ตามที่ lemma ยืนยันว่าใช้ได้กับสตริงที่ยาวพอทั้งหมดโดยมีการแบ่งบางส่วนสำหรับทั้งหมด $k$หนึ่งตัวอย่างก็เพียงพอแล้ว ตัวอย่างไม่มีที่สิ้นสุดไม่ได้พิสูจน์อะไร