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

18

É 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.

J.-E. PIN
fonte

Respostas:

9

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 XXMGMwXMGwXque 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).ML(G)XG

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 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 } :D1,D2,...{1}DiiGX1n{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.n1n
  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 ).Diii=nccDiii
  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 .Di1iDiDii
  4. Se rejeita 1 i , substituir toda a fita com os não-terminais que produzem . Caso contrário, falhe.Di 1i1

Tomamos . Claramente para qualquer , uma vez que .X=L(GX)XL(Di)i1i+cX1i+cL(Di)


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 .)XGX

Seja uma TM arbitrária. Convertemos em um CSG que se comporta da seguinte forma na sequência de análise :MMG1n

  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.n2
  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.MMM
  3. Se , comporte-se como . Se tivéssemos que terminar a simulação, falharíamos.MGX

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 mX X L ( G )MGMnMG1mmn+21mXXL(G) não é regular. Por outro lado, se M nunca parar, então L ( G ) =L(G)M é claramente regular.L(G)=

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

gdmclellan
fonte
2
Para a primeira parte de sua resposta, e { a pp  são primos } são exemplos de linguagens não regulares unárias, sensíveis ao contexto. {an2n0}{app is prime}
J.-E.
Heh, na verdade exagerado, provavelmente deveria ter me ocorrido que um argumento diagonal seria um exagero grosseiro. Acho que vou editar uma nota na resposta. Espero que a segunda parte tenha sido útil, no entanto.
Gdmclellan
@ J.-E.Pin: Eu não pensei muito sobre isso, é fácil criar uma gramática unária sensível ao contexto para ? {app is prime}
Marzio De Biasi
@ marzio-de-biasi Tenho que confessar que não me verifiquei, mas confiei nesta resposta
J.-E.
@MarzioDeBiasi Muito fácil. Ao determinar se uma linguagem é sensível ao contexto, o processo usual é algo como 1. não-deterministicamente adivinhe a sequência de análise; 2. realize alguma computação limitada ao espaço para determinar se a sequência de análise satisfaz algum predicado; e 3. gerar a cadeia se o referido predicado for considerado satisfeito. O espaço pode ser um pouco problemático (o espaço vinculado é fornecido pelo comprimento da sequência de análise, porque você não pode contratar uma sequência derivada usando produções sensíveis ao contexto), mas no caso unário, você tem espaço exponencial para trabalhar .
gdmclellan
6

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 na nN  e  m n : a mL } . Então claramente L ' é regular se e somente se L estiver vazio.NaLaL={ananN and mn:amL}LL

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

Georg Zetzsche
fonte
"o vazio é indecidível para linguagens unárias sensíveis ao contexto": é um fato bem conhecido? Você teria uma referência?
J.-E.
1
Dada uma linguagem sensível ao contexto , use o morfismo h : Σ{ a } que mapeia todas as letras para a . Então h ( L ) está vazio se e somente se L estiver vazio. Para o espaço de registro determinístico, dado um TM T , pode-se construir um det. logspace TM para o conjunto de todos um 2 n , tais que T tem uma computação suspensão de comprimento n . LΣh:Σ{a}ah(L)LTa2nTn
Georg Zetzsche 27/06