Язык списков слов, не все из которых разные, не без контекста

Question

Как доказать, что следующий язык не содержит контекст, используя насосную лемму? $$ L={w_1 \ # w_2 \ # \ dots \ #w_k \ colon k ≥ 2, w_i \ in \ {0,1 \} ^ *, w_i= w_j \ text {Для некоторых} i \ ne j \} $$

У меня проблемы с выбором строки для использования для доказательства.Я знаю, что я должен выбрать так, чтобы как минимум две подстроки, разделенные #, равны друг другу, но не уверены в том, как приблизиться к этому.Если кто-то мог, пожалуйста, помогите мне с этим, я был бы признателен за это.

Answer 1

Если $ l $ , были бы без контекста, то $ l '= d (l \ cap (0+1) ^ * \ # (0 + 1) ^ *) $ be, где $ d $ - это гомоморфизм, который удаляет $ \ # $ .Однако $ l '$ - это язык квадратов (слова формы $ W ^ 2 $ ), что известно, чтобы не быть без контекста.

Если по какой-то причине вы должны доказать, что $ l $ не содержит контекстных непосредственно с использованием накачки леммы, это говорит о том, чтобы смотреть доказательство, которое $ l '$ не содержит контекстных и пытаться адаптировать его.