Linguagens decentes não sensíveis ao contexto

É possível argumentar que a maioria das linguagens criadas para descrever os problemas do dia a dia são sensíveis ao contexto. Por outro lado, é possível e não difícil encontrar alguns idiomas que não sejam recursivos ou mesmo não recursivamente enumeráveis.

Entre esses dois tipos estão as linguagens recursivas não sensíveis ao contexto. A Wikipedia dá um exemplo aqui :

Um exemplo de linguagem recursiva que não é sensível ao contexto é qualquer linguagem recursiva cuja decisão seja um problema difícil do EXPSPACE, digamos, o conjunto de pares de expressões regulares equivalentes com exponenciação.

Portanto, a pergunta: que outros problemas existem que são decidíveis, mas ainda não sensíveis ao contexto? Essa classe de problemas é a mesma que o EXPSPACE difícil decidível?

CSL é o mesmo que $\mathsf{NSpace}(n)$ (espaço linear não determinístico). Qualquer idioma que esteja fora de não é CSL.$\mathsf{NSpace}(n)$

Para ter uma idéia da situação, lembre-se que e até TQBF.$SAT \in \mathsf{NSpace}(n)$

Que outros problemas existem que são decidíveis, mas não são sensíveis ao contexto?

Existem muitos problemas. Qualquer problema que esteja completo para uma classe de complexidade maior que será suficiente (precisamos de P S p a c e porque problemas como TQBF em N S p a c e ( n ) que estão completos para P S p a c $\mathsf{PSpace}$$\mathsf{PSpace}$$\mathsf{NSpace}(n)$$\mathsf{PSpace}$porque uma redução (tempo polinomial) pode aumentar o tamanho de uma entrada por um polinômio). Dar um exemplo significa provar um limite inferior para a classe de complexidade que contém o problema e essa é uma tarefa muito, muito difícil. A única maneira importante de sabermos até agora é a diagonalização, o que intuitivamente significa que a classe maior deve ser capaz de simular a classe menor.

Então parece um lugar natural para começar a olhar para exemplos naturais de linguagem que não são CSL.$\mathsf{ExpSpace\text{-}hard}$

Essa classe de problemas é a mesma que o EXPSPACE difícil decidível?

Não. Pelo teorema da hierarquia espacial , existem idiomas que estão em que não estão em N S p a c e ( n ) . Se você está pedindo bons exemplos, isso será difícil, porque o teorema funciona usando diagonalização e, portanto, a linguagem que prova satisfazer essas condições é muito artificial.$\mathsf{NSpace}(n^2)$$\mathsf{NSpace}(n)$

Sugiro que você faça uma pergunta separada para um problema natural que separa de N S p a c e ( n ) .$\mathsf{NSpace}(n^2)$$\mathsf{NSpace}(n)$

Assim como é livre de contexto, mas não regular, o idioma L = { a n b n c n : n ≥ 0 } é decidível, mas não é livre de contexto. No entanto, L pode ser resolvido usando o espaço logarítmica (você só precisa de um contador para cada um dos símbolos a , b e c ), por isso não é EXSPACE-duro.$\{a^nb^n:n\geq 0\}$$L=\{a^nb^nc^n:n\geq 0\}$$L$$a$$b$$c$

Além disso, o idioma , onde r 1 e r 2 são expressões regulares, é completo no PSPACE. Tenho quase certeza de que não é sensível ao contexto, mas não me lembro de uma prova e estou escrevendo no meu telefone, por isso não é fácil procurar referências.$\{(r_1,r_2):L(r_1)=L(r_2)\}$$r_1$$r_2$