لغة قوائم الكلمات، وليس كلها مختلفة، ليست خالية من السياق

Question

كيف يمكنني إثبات أن اللغة التالية ليست خالية من السياق باستخدام Lemma الضخ؟ $$ l={w_1 \ # w_2 \ # \ dots \ #w_k \ colon k ≥ 2، w_i \ in \ {0،1 \} ^ *، w_i= w_j \ text {for some} i \nn j \}

أواجه مشكلة في اختيار السلسلة لاستخدامها للإثبات.أعلم أنه لا بد لي من اختيار سلسلة بحيث لا تقل عن سراحان على الأقل مفصولة عن طريق # متساوين بعضهما البعض ولكني غير متأكد من كيفية الاقتراب من ذلك.إذا كان شخص ما يمكن أن يساعدني في هذا، فسأكون ممتنا له.

Answer 1

إذا كانت $ L $ كانت خالية من السياق، لذلك سوف $ l '= d (l \ cap (0+1) ^ * \ # (0 + 1) ^ *) $ يكون، حيث $ D $ هو homomoraphism الذي يحذف $ \ # $ .ومع ذلك، $ l $ هي لغة المربعات (كلمات النموذج $ w ^ 2 $ )، والتي هي معروفة لا تكون خالية من السياق.

إذا كان لديك لسبب ما لديك لإثبات أن $ L $ ليست خالية من السياق مباشرة باستخدام Lemma الضخ، وهذا يشير إلى النظر إلى دليل على $ L $ خالية من السياق ومحاولة تكييفها.