Sprache der Listen von Wörtern, die nicht alle unterscheiden, ist nicht kontextfrei

Question

Wie beweise ich, dass die folgende Sprache mit dem Pump-Lemma nicht kontextfrei ist? $$ L={w_1 \ # W_2 \ # \ dots \ #w_k \ colon k ≥ 2, w_i \ in \ {0,1 \} ^ *, w_i= w_j \ text {für einige} i \ ne j \} $$

Ich habe Probleme, die Zeichenfolge zu wählen, die für den Beweis verwendet wird.Ich weiß, dass ich eine Saite auswählen muss, so dass mindestens zwei von den # getrennte Teilzeichenfolgen gleich einander sind, aber nicht sicher bin, wie man sich nähern kann.Wenn jemand bitte mit diesem helfen könnte, würde ich es schätzen.

Answer 1

wenn $ L $ kontextfrei war, dann würde also $ l '= d (l \ cap (0+1) ^ * \ # (0 + 1) ^ *) $ Seien Sie, wobei $ D $ der Homomorphismus ist, der $ \ # $ . $ l '$ ist die Sprache der Quadrate (Wörter des Formulars $ w ^ 2 $ )Das ist bekannt, das bekannt ist, nicht kontextfrei zu sein.

Wenn Sie aus irgendeinem Grund nachweisen müssen, dass $ L $ nicht direkt mit dem Pump-Lemma kontextfrei ist, deuten darauf hin, dass der Nachweis der $ l '$ ist nicht kontextfrei und versucht es anzupassen.