سؤال لغة خالية من السياق (ضخ ليما)

Question

أعلم أن هذا لا يرتبط مباشرة بالبرمجة ، لكنني كنت أتساءل عما إذا كان أي شخص يعرف كيفية تطبيق Lemma الضخ على الدليل التالي:

اظهر ذلك l = {(a^n) (b^n) (c^m): n! = m} ليست لغة خالية من السياق

أنا واثق تمامًا من تطبيق ضخ الليمون ، لكن هذا الأمر يزعجني حقًا. ما رأيك؟

Answer 1

تحرير: كنت أقودك تمامًا إلى المسار الخطأ. هذا ما يحدث عندما أحاول المساعدة عندما لم أحلل المشكلة بنفسي تمامًا.

أوجدين ليما

لنفترض أن L خالٍ من السياق. بقلم Ogden's Lemma ، يوجد عدد صحيح P يحتوي على الخصائص التالية:

بالنظر إلى سلسلة W في L على الأقل P رموز P طويلة ، حيث تم تمثيل P على الأقل من هذه الرموز ، يمكن تمثيل W على أنها UVXYZ ، والتي ترضي:

1. X لديه رمز واحد على الأقل ملحوظ ،
2. إما u و v على حد سواء لديهم رمز ملحوظ أو y و z على حد سواء الرموز المميزة ،
3. لدى Vxy على معظم الرموز ذات العلامات P ، و
4. الأشعة فوق البنفسجية^أنا xy^أنا Z في L لـ i> = 0

هذا هو أوجدين ليما. الآن ، دع Q يكون عدد صحيح قابلة للقسمة بواسطة كل عدد صحيح إيجابي ليس أكبر من p. دع w = أ^P+Q. ب^P+Q. ج^ص. ضع علامة على كل ج. بحلول #2 ، يجب أن تحتوي U أو V على واحد على الأقل ج. إذا كان u أو v يحتوي على أي رمز آخر ، فإن #4 يفشل ، لذلك يجب أن يحتوي u و v فقط c. ولكن بعد ذلك ، يفشل #4 عندما i = q/| uv |. نحن نعلم Q قابلة للقسمة بواسطة | UV | لأن p> | الأشعة فوق البنفسجية | > 0 ، و Q قابلة للقسمة بواسطة جميع الأعداد الصحيحة الإيجابية أقل من ص.

لاحظ أن Lemma من Ogden يتحول إلى Lemma الضخ عند وضع علامة على جميع الرموز.

ضخ ليما

لنفترض أن L خالٍ من السياق. من خلال ضخ Lemma ، هناك طول P (ليس بالضرورة نفس P على النحو الوارد أعلاه) بحيث يمكن تمثيل أي سلسلة W في L كـ UVXYZ ، حيث

1. | vxy | <= P ،
2. | vy | > = 1 ، و
3. الأشعة فوق البنفسجية^أنا xy^أنا Z في L لـ i> = 0.

بالنظر إلى سلسلة W في l ، إما m> n أو m <n. افترض P = 2.

لنفترض أن م> ن. (لاحظ أن λ تشير إلى السلسلة الفارغة.)

• دعك = أ^ن ب^ن ج^M-1
• دع V = C
• دع x = λ
• دع y = λ
• دع z = λ

لنفترض أن n> m.

• دعك = أ^N-1
• دع v = أ
• دع x = λ
• دع y = ب
• دع z = ب^N-1 ج^م

يوضح هذا أنه لا توجد سلسلة من L توفر مثالًا مضادًا باستخدام Lemma الضخ إلى الافتراض بأن L هي لغة خالية من السياق (على الرغم من أنها حساسة للسياق).