Linguagem de listas de palavras, nem todas as quais são diferentes, não é livre de contexto

Question

Como faço para provar que a seguinte língua não é livre de contexto usando o lema de bombeamento? $$ L= {w_1 \ # w_2 \ # \ Dots \ #w_k \ colon k ≥ 2, w_i \ in \ {0,1} ^ *, w_i= w_j \ text {para alguns} i \ ne j} $$

Estou com problemas para escolher a string para usar para a prova.Eu sei que tenho que escolher uma string tal que pelo menos duas substrings separadas pelo # são iguais umas às outras, mas não tenho certeza de como abordar isso.Se alguém pudesse me ajudar com isso, eu apreciaria isso.

Answer 1

Se $ l $ fosse livre de contexto, então seria $ l '= d (l \ cap (l \ cap (0+1) ^ * \ # (0 + 1) ^ *) $ seja, onde $ D $ é o homomorfismo que exclui a matemática $ \ # $ .No entanto, $ l '$ é a linguagem dos quadrados (palavras da forma $ w ^ 2 $ ), que é bem conhecido não ser livre de contexto.

Se por algum motivo você tiver que provar que $ l $ não é livre de contexto usando o Lema de bombeamento, isso sugere olhar para a prova de que $ l '$ não é livre de contexto e tentando adaptá-lo.