Pode haver um lema de bombeamento sensível ao contexto?

Sabe-se que uma propriedade "bombear" (palavras de um determinado comprimento implica a existência de loops no mecanismo de definição de idioma) para linguagens regulares e sem contexto e mais algumas (geralmente usadas para refutar a associação de um idioma a uma determinada classe) )

Na discussão em torno dessa pergunta , a resposta de Daisy sugere que não pode haver um lema de bombeamento para linguagens sensíveis ao contexto - uma vez que são muito complexas.

Isso é verdade - pode ser demonstrado que não pode haver algum tipo de propriedade de bombeamento - e há uma boa referência para isso (ou contra isso)?

Aqui estão algumas evidências de que não há lema de bombeamento para as linguagens sensíveis ao contexto.

Obviamente, uma resposta depende da questão do que constitui um lema de bombeamento. A definição razoável mais fraca que eu conseguia pensar é a seguinte: Uma classe de linguagem tem um lema de bombeamento se houver um predicado ternário decidível que significa:$\mathcal{C}$$P(\cdot,\cdot,\cdot)$$P(g,w,d)$

• $g$ é uma palavra que codifica um idioma de (pense em gramática),$L(g)$$\mathcal{C}$
• $w$ é uma palavra no idioma codificado por$g$
• $d$ é uma palavra que codifica uma computação / derivação bombeável para (pense: computação NFA com estado repetido ou árvore de derivação CFG com repetição não-terminal). Aqui, bombeável significa: existem infinitas palavras em .$w$$L(g)$

Além disso, queremos que, dada uma linguagem em codificada por , para cada palavra suficientemente longa , exista uma palavra tal que .$L$$\mathcal{C}$$g$$w\in L$$d$$P(g,w,d)$

Por exemplo, o lema de bombeamento para idiomas regulares daria origem ao predicado " codifica um NFA e codifica uma execução que repete um estado e lê ". Para codificações adequadas, isso satisfaz claramente as condições acima.$g$$\varepsilon$$d$$w$

Agora vamos mostrar que esse predicado não existe para as linguagens sensíveis ao contexto.

Observe que, se uma aula de língua tem um lema do bombeamento, então o problema infinito (Dada uma gramática, não é gerar uma linguagem infinita?) É recursivamente enumeráveis: Dada uma codificação , podemos enumerar palavras e e verificar se . Se encontrarmos tal , responderemos 'yes', caso contrário, continuaremos a enumeração.$g$$w$$d$$P(g,w,d)$$w,d$

No entanto, mostramos que o problema do infinito para as linguagens sensíveis ao contexto não é recursivamente enumerável. Lembre-se de que é um nível da hierarquia aritmética que inclui estritamente os idiomas recursivamente enumeráveis. Portanto, basta provar:$\Pi_2^0$

Reivindicação : O problema do infinito para as linguagens sensíveis ao contexto é -completo.$\Pi_2^0$

É sabido que o problema do infinito para linguagens recursivamente enumeráveis ​​é -completo (mais frequentemente, encontra-se a formulação de que o problema de finitude é -complete). Portanto, basta reduzir o último problema ao problema do infinito para as linguagens sensíveis ao contexto.$\Pi_2^0$$\Sigma_2^0$

Dado um TM , construímos um LBA para o idioma Então, é infinito se é infinito, o que completa nossa prova.$M$$A$

Atualização: tentou ser mais claro. Atualização: Exemplo adicionado.