Existe um exemplo de uma linguagem recursiva que não é sensível ao contexto?

7

Eu tenho procurado uma linguagem prototípica para linguagens recursivas (decidíveis) que não seja sensível ao contexto sem sucesso. Por exemplo, é prototípico de linguagens regulares, para linguagens livres de contexto e para linguagens sensíveis ao contexto. Eu costumo considerar a linguagem que é aceita por uma máquina universal de Turing (UTM) como prototípica de recursivamente enumerável. No entanto, para os idiomas recursivos, não tenho um. Eu costumava pensar que era recursivo, mas a verificação de um número é primo pode ser feita por uma máquina de Turing limitada. Eu também tinha mas novamente verificando isso pode ser feito por uma máquina de Turing limitada.aanbnanbncn{1p|p is prime}{12n}

Por outro lado, as outras opções que encontrei são as máquinas de Turing que exigem que a saída da computação seja armazenada em algum lugar da máquina; no entanto, a saída não faz parte da linguagem aceita, que torna regular ou contextualizada a linguagem. grátis até agora. Por exemplo, a máquina que soma dois números representados por 1s e separados por um espaço e coloca o resultado depois. Nesse caso, o idioma aceito é na verdade que é regular! Se tentarmos fazê-lo como verificação, se tornarmos livres de contexto mas não recursivos!1B11nB1mB1n+m

Então, é possível falar sobre uma linguagem recursiva que pode ser regular em essência, mas como está condicionada a fazer o cálculo e colocar um resultado na saída como um tipo de linguagem recursiva? Definitivamente, isso não pode ser feito em uma máquina de Turing limitada.

Ivan Meza
fonte
Linguagens sensíveis ao contexto são equivalentes às linguagens que podem ser decididas por máquinas de Turing com limite linear . Assim, qualquer decidable linguagem por um (não LBA) TM geral, não será sensível ao contexto (mas sim, pode ser gerada por uma gramática irrestrita )
Ran G.
11
Se você quiser um exemplo específico, pense em idiomas no formato . L={M,xM accepts x within |x|10 steps}
Ran G.
Uau, excelente! Deixa comigo! Este é sempre decidível, pois só tenho que simular M passos! Muito obrigado! 10
Ivan Meza
Desde LINSPACE ® R, sim.
Raphael

Respostas:

6

Aqui está uma prova mais formal, pelo truque padrão da diagonalização (deve ser folclore, mas vi recentemente aqui )

Permita que seja uma enumeração de gramáticas sensíveis ao contexto (convença-se de que só existem muitas delas contáveis; por que elas podem ser enumeradas?),G1,G2,...

Seja enumeração de (ou seja, , , , etc. no caso do alfabeto binário).x1,x2,,Σx1=ϵx2=0x3=1x4=00

Considere o idioma:

L={xixiL(Gi)}.

A reivindicação 1 não é sensível ao contexto: se era, havia um específico gerando-o, mas enquanto .LGjxjLxjGj

A reivindicação 2 é decidível: dado , apenas verificamos se gera (esse problema é conhecido como PSPACE completo, portanto, decidível).LxiGi

Tocou.
fonte
Este é tão legal que li algo assim para estabelecer a relação sobre complementos da família de idiomas. Mas usar essa construção para restringir a sensibilidade ao contexto, mantendo-a recursiva, é muito legal!
Ivan Meza