Decidir se uma linguagem sensível ao contexto unária é regular

É um resultado bem conhecido que a pergunta

Uma gramática sem contexto gera uma linguagem comum?

é indecidível. No entanto, torna-se decidível em um alfabeto unário, simplesmente porque, neste caso, as classes de linguagens livres de contexto e regulares coincidem.

Minha pergunta é saber o que acontece com linguagens sensíveis ao contexto unárias .

É decidido saber se uma determinada gramática sensível ao contexto em um alfabeto unário gera um idioma comum.

Se a resposta for positiva, uma estimativa da complexidade seria bem-vinda.

Infelizmente, seu problema é indecidível. A abordagem que me deparei (que pode ser exagerada, para que qualquer pessoa que tenha uma abordagem mais conveniente deva avançar!) Primeiro usa um argumento diagonal para demonstrar que existe um CSL unário que não é regular (em contraste com o resultado positivo para CFLs unárias) e, em seguida, reduz-se do problema de parada para máquinas de Turing ao, dado um TM M , construir um CSG G que simula M em um comprimento de fita menor que a sequência de análise w , reconhecendo X se M parar sem ultrapassar seus limites e falhando em analisar de outra forma, para que G analise com êxito tudo w ∈ $X$$M$$G$$M$$w$$X$$M$$G$$w \in X$que são suficientemente longos se parar (de modo que L ( G ) difere de X apenas em muitas seqüências finitas e, portanto, não pode ser regular), caso contrário, G reconhece o idioma vazio (que é claramente regular).$M$$L(G)$$X$$G$

A chave para essa abordagem é a observação de que os CSGs não se preocupam apenas com questões gramaticais, como a estrutura das frases - na verdade, as seqüências de derivação do CSG podem realizar cálculos arbitrários, não determinísticos e limitados ao espaço (de fato, existem $\mathbf{PSPACE}$-complete CSLs) antes de começar o negócio de alinhar com a sequência de análise. Isso é mais facilmente observado através de conversões padrão entre CSGs e gramáticas monotônicas (que continuam a funcionar quando restritas a alfabetos unários) e o uso de produções monotônicas simples para simular transições de máquinas de Turing em seqüências de derivação que representam estágios em um histórico de computação. Ao longo desta resposta, vou assumir que o leitor pode intuir a maioria dos detalhes quando um CSG é necessário para simular um determinado cálculo. (Eu suponho que o solicitante esteja confortável com tudo isso, mas estou analisando a questão por completo. No entanto, sinta-se à vontade para solicitar esclarecimentos nos comentários.)

Em primeiro lugar, precisamos do nosso CSG unário não regular. ( EDIT: portanto, isso foi um exagero - CSLs unárias não regulares podem ser facilmente exibidas, por exemplo, através do lema de bombeamento em qualquer idioma que mostre a não regularidade mais básica. Veja os comentários para exemplos. Em retrospectiva, usando um argumento diagonal era como levar uma ogiva nuclear a uma luta com facas. Examine esta construção se você estiver curioso, caso contrário, pule para a redução.)

Vamos ser uma enumeração de AFDs sobre alfabeto { 1 } , de tal modo que o número de estados em D i aumenta em i . Descrevemos um CSG G X em termos de seu comportamento ao analisar a string 1 n ∈ { 1 } ∗ :$D_1, D_2, ...$$\{1\}$$D_i$$i$$G_X$$1^n \in \{1\}^*$

1. Gere não-deterministicamente uma sequência de terminais não "em branco", que consideramos a "fita". Um dos não terminais em branco deve ser um não terminal "em branco + cabeça de leitura e gravação + estado inicial". Se a sequência de análise não for 1 n , essa derivação acabará falhando. Descrevemos o restante do processo em termos da computação determinística simulada pela única derivação possível.$n$$1^n$
2. Imprimir na fita uma codificação de seguido do número i em binário, onde i = n - c e c é escolhido de modo que sempre tem espaço suficiente na nossa fita para fazer o que precisamos. (Isto é possível uma vez que o espaço necessário para codificar tanto D i e i cresce logaritmicamente em i ).$D_i$$i$$i = n - c$$c$$D_i$$i$$i$
3. Avaliar na entrada 1 i . Isso não exige um representando D i tape 's - você pode apenas armazenar um único estado, que mudam de acordo com as transições de D i como você decrementar i .$D_i$$1^i$$D_i$$D_i$$i$
4. Se rejeita 1 i , substituir toda a fita com os não-terminais que produzem . Caso contrário, falhe.$D_i$ $1^i$$1$

Tomamos . Claramente para qualquer , uma vez que .$X = L(G_X)$$X \ne L(D_i)$$i$$1^{i+c} \in X \Leftrightarrow 1^{i+c} \notin L(D_i)$

O próximo passo é projetar uma redução do problema de parada para o problema do solicitante. (Se você pulou a seção acima, seja uma CSL unária não regular arbitrária gerada pelo CSG .)$X$$G_X$

Seja uma TM arbitrária. Convertemos em um CSG que se comporta da seguinte forma na sequência de análise :$M$$M$$G$$1^n$

1. Gere não terminais em branco, o mais à esquerda sendo o terminal em branco + cabeça de leitura e gravação não terminal, e também gere um não terminal "limite" em cada lado. Novamente, se gerarmos o número errado de não terminais, falharemos.$n-2$
2. Simule no espaço entre os não terminais de limite. Se mudar para um dos estados de contorno, encerraremos a simulação e assumiremos que nunca para.$M$$M$$M$
3. Se , comporte-se como . Se tivéssemos que terminar a simulação, falharíamos.$M$$G_X$

Observe que se conseguir rodar para sempre dentro dos limites, nunca poderá gerar uma sequência de análise e, portanto, falhará. Se parar, então há uma quantidade de espaço suficiente para conter toda a computação de ; portanto, analisa sempre que e e, portanto, é a união de e uma linguagem finita, de ondeG M n M G 1 m m ≥ n + 2 1 m ∈ X X L ( G $M$$G$$M$$n$$M$$G$$1^m$$m \ge n+2$$1^m \in X$$X$$L(G)$ não é regular. Por outro lado, se M nunca parar, então L ( G ) $L(G)$$M$ é claramente regular.$L(G) = \varnothing$

Um algoritmo para decidir se é regular ou não determinaria se M parou ou não em uma fita em branco, o que é indecidível. Daqui resulta que o problema do solicitante é indecidível.$L(G)$$M$

Esta é essencialmente a mesma resposta que acima, mas como uma resposta "mais conveniente" é procurada, estou mencionando o seguinte: (Além disso, este é o meu primeiro post aqui, então me perdoe se eu estiver postando uma trivialidade!)

Observe que o vazio é indecidível para linguagens unárias sensíveis ao contexto. Corrija uma linguagem sensível ao contexto, mas não regular . Dado um LBA para L ⊆ a ∗ , pode-se construir facilmente um LBA para L ′ = { a n ∣ a n ∈ N  e  ∃ m ≤ n : a m ∈ L } . Então claramente L ' é regular se e somente se L estiver vazio.$N\subseteq a^*$$L\subseteq a^*$$L'=\{ a^n \mid \text{$a^n\in N$ and $\exists m\le n\colon a^m \in L$}\}$$L'$$L$

Atualização: Obviamente, o mesmo argumento mostra que a indecidibilidade já é válida para o espaço logarítmico determinístico.