El lenguaje de listas de palabras, no todas las cuales son diferentes, no es libre de contexto.

Question

¿Cómo demuestro que el siguiente idioma no está libre de contexto usando el lemma de bombeo? $$ L={w_1 \ # w_2 \ # \ dots \ #w_k \ colon k ≥ 2, w_i \ in \ \ {0,1 \ \ in \ \ {0,1 \ \ in \ \ {0,1 \ \ in \ \ {0,1} ^ *, w_i= w_j \ text {para algunos} i \ ne j \} $$

Tengo problemas para elegir la cadena para usar para la prueba.Sé que tengo que elegir una cadena de modo que al menos dos subcadenas separadas por el # sean iguales entre sí, pero no estoy seguro de cómo abordar esto.Si alguien pudiera ayudarme con esto, lo apreciaría.

Answer 1

Si $ l $ fue libre de contexto, entonces lo haría $ l '= d (l \ cap (0+1) ^ * \ # (0 + 1) ^ *) $ BE, donde $ d $ es el homomorfismo que elimina $ \ # $ .Sin embargo, $ l '$ es el idioma de los cuadrados (palabras del formulario $ w ^ 2 $ ), que es bien conocido no ser libre de contexto.

Si por alguna razón tiene que demostrar que $ l $ no está libre de contexto directamente con el LEMMA de bombeo, lo sugiere que está buscando la prueba de que $ L '$ no es libre de contexto y tratando de adaptarlo.