Langue des listes de mots, qui ne sont pas toutes différentes, n'est pas sans contexte

Question

Comment puis-je prouver que la langue suivante n'est pas sans contexte en utilisant le lemme de pompage? $$ L={w_1 \ # w_2 \ # \ points \ #w_k \ côlon k ≥ 2, w_i \ in \ \ {0,1 \} ^ *, w_i= w_j \ text {pour certains} i \ ne j $$

J'ai du mal à choisir la chaîne à utiliser pour la preuve.Je sais que je dois choisir une chaîne de telle sorte que au moins deux sous-chaînes séparées par le # soient égales les unes aux autres mais ne savent pas comment approcher cela.Si quelqu'un pouvait m'aider avec ça, je l'apprécierais.

Answer 1

si $ l $ était exempt de contexte, alors $ l '= d (l \ cap (0+1) ^ * \ # (0 + 1) ^ *) $ soit, où $ d $ est l'homomorphisme qui supprime $ \ # $ .Cependant, $ l '$ est la langue des carrés (mots de la forme $ w ^ 2 $ ), qui est bien connu pour ne pas être exempt de contexte.

Si pour une raison quelconque, vous devez prouver que $ l $ n'est pas directement sans contexte en utilisant le lemme de pompage, cela suggère de regarder la preuve que $ l '$ n'est pas exempt de contexte et d'essayer de l'adapter.