¿Puede haber un lema de bombeo sensible al contexto?

Se sabe que existe una propiedad de "bombeo" (las palabras de cierta longitud implican la existencia de bucles en el mecanismo de definición del lenguaje) para los lenguajes regulares y libres de contexto y algunos más (generalmente utilizados para refutar la pertenencia de un idioma a una determinada clase) )

Dentro de la discusión en torno a esta pregunta , la respuesta de Daisy sugiere que no puede haber un gran lema para los lenguajes sensibles al contexto, ya que son tan complejos.

¿Es eso cierto? ¿Se puede demostrar que no puede haber algún tipo de propiedad de bombeo? ¿Hay alguna buena referencia para eso (o en contra de eso)?

Aquí hay alguna evidencia de que no hay un lema de bombeo para los lenguajes sensibles al contexto.

Por supuesto, una respuesta depende de la pregunta qué constituye un lema de bombeo. La definición razonable más débil que se me ocurre es esta: una clase de lenguaje tiene un lema de bombeo si hay un predicado ternario decidible donde medio:$\mathcal{C}$$P(\cdot,\cdot,\cdot)$$P(g,w,d)$

• $g$ es una palabra que codifica un lenguaje de (piense: gramática),$L(g)$$\mathcal{C}$
• $w$ es una palabra en el lenguaje codificado por$g$
• $d$ es una palabra que codifica una computación / derivación bombeable para (piense: computación NFA con estado repetido o árbol de derivación CFG con no terminal repetido). Aquí, bombeable significa: existen infinitas palabras en .$w$$L(g)$

Además, queremos que, dado un lenguaje en codificado por , por cada palabra suficientemente larga , exista una palabra tal que .$L$$\mathcal{C}$$g$$w\in L$$d$$P(g,w,d)$

Por ejemplo, el lema de bombeo para los lenguajes regulares daría lugar al predicado " codifica un sin y codifica una ejecución que repite un estado y lee ". Para codificaciones adecuadas, esto satisface claramente las condiciones anteriores.$g$$\varepsilon$$d$$w$

Ahora demostremos que dicho predicado no existe para los lenguajes sensibles al contexto.

Observe que si una clase de lengua tiene un lema de bombeo, entonces el problema infinito (Dada una gramática, ¿se generará un lenguaje infinito?) Es recursivamente numerable: Dada una codificación , podemos enumerar palabras y y comprobar si . Si encontramos tal , respondemos 'sí', de lo contrario, continuamos la enumeración.$g$$w$$d$$P(g,w,d)$$w,d$

Sin embargo, mostramos que el problema de infinito para los lenguajes sensibles al contexto no es recursivamente enumerable. Recuerde que es un nivel de la jerarquía aritmética que incluye estrictamente los lenguajes recursivamente enumerables. Por lo tanto, es suficiente demostrar:$\Pi_2^0$

Reclamación : El problema de infinito para los lenguajes sensibles al contexto es -complete.$\Pi_2^0$

Es bien sabido que el problema de infinito para lenguajes recursivamente enumerables es -completo (más a menudo, se encuentra la formulación de que el problema de finitud es -completo). Por lo tanto, es suficiente reducir el último problema al problema de infinito para los lenguajes sensibles al contexto.$\Pi_2^0$$\Sigma_2^0$

Dado un TM , construimos un LBA para el lenguaje Entonces, es infinito si es infinito, lo que completa nuestra prueba.$M$$A$

Actualización: Intenté ser más claro. Actualización: ejemplo agregado.