Algoritmo para testar se um idioma é livre de contexto

18

Existe um algoritmo / procedimento sistemático para testar se uma linguagem é livre de contexto?

Em outras palavras, dado um idioma especificado em forma algébrica (pense em algo como ), teste se o idioma é livre de contexto ou não . Imagine que estamos escrevendo um serviço da Web para ajudar os alunos com todos os seus trabalhos de casa; você especifica o idioma e o serviço da web gera "sem contexto" ou "sem contexto". Existe alguma boa abordagem para automatizar isso?eu={umanbnuman:nN}

Obviamente, existem técnicas para a prova manual, como o lema de bombeamento, o lema de Ogden, o lema de Parikh, o lema de intercâmbio e muito mais aqui . No entanto, cada um deles exige uma visão manual em algum momento, portanto, não está claro como transformar qualquer um deles em algo algorítmico.

Vejo que Kaveh escreveu em outro lugar que o conjunto de linguagens sem contexto não é recursivamente enumerável, então parece que não há esperança de que algum algoritmo funcione em todas as linguagens possíveis. Portanto, suponho que o serviço da Web precise ser capaz de gerar "sem contexto", "sem contexto" ou "não sei dizer". Existe algum algoritmo que muitas vezes seria capaz de fornecer uma resposta diferente de "não sei dizer", em muitos dos idiomas que provavelmente nos livros didáticos? Como você criaria um serviço da Web?


Para tornar essa questão bem formulada, precisamos decidir como o usuário especificará o idioma. Estou aberto a sugestões, mas estou pensando em algo assim:

eu={E:S}

onde é uma expressão de palavras e é um sistema de desigualdades lineares sobre as variáveis ​​de comprimento, com as seguintes definições:ES

  • Cada um de x,y,z,... é uma expressão de palavra. (Eles representam variáveis ​​que podem conter qualquer palavra em Σ .)

  • Cada um de a, b, c, \ dotsuma,b,c,... é uma expressão de palavra. (Implicitamente, Σ={uma,b,c,...} , então uma,b,c,... representam um único símbolo no alfabeto subjacente.)

  • Cada umaη,bη,cη,... é uma expressão de palavra, se η for uma variável de comprimento.

  • A concatenação de expressões de palavras é uma expressão de palavras.

  • Cada um de é uma variável de comprimento. (Eles representam variáveis ​​que podem conter qualquer número natural.)m,n,p,q,...

  • Cada um dos pontos é uma variável de comprimento. (Eles representam o comprimento de uma palavra correspondente.)|x|,|y|,|z|,...

Isso parece amplo o suficiente para lidar com muitos dos casos que vemos nos exercícios de livros didáticos. Obviamente, você pode substituir qualquer outro método textual de especificar um idioma em forma algébrica, se desejar.

DW
fonte
Não seria mais fácil começar com a regularidade dos idiomas?
Yuval Filmus
@YuvalFilmus, com certeza! Agora que você mencionou, é uma ótima ideia. Você acha que o problema é viável para idiomas comuns? Ficaria feliz em perguntar um correspondente sobre idiomas regulares, se você acha que isso pode ser valioso.
DW
2
Certamente seria mais fácil para idiomas comuns. A propósito, a não-decidibilidade geral não se aplica necessariamente aos idiomas do formulário que você menciona.
Yuval Filmus
4
Receio que esse problema esteja provavelmente aberto, pelo menos um caso específico é: cstheory.stackexchange.com/questions/17976 . Pode haver uma maneira de obter indecidibilidade para o seu problema mais geral, mas não o vejo.
Sdcvvc
seria útil dar exemplos de palavras no idioma. sugerir mais pesquisas / colaborações no Computer Science Chat
vzn

Respostas:

0

Pelo teorema de Rice , verificar se a linguagem aceita por uma máquina de Turing tem alguma propriedade não trivial (aqui: ser livre de contexto) não é decidível. Portanto, você teria que restringir o poder do seu mecanismo de reconhecimento (ou descrição) para torná-lo não Turing completo, na esperança de obter uma resposta.

Para algumas descrições de idiomas, a resposta é trivial: se for por expressões regulares, é regular, portanto, livre de contexto. Se for por gramáticas livres de contexto, idem.

vonbrand
fonte
Concordo com todos os seus comentários, mas não tenho certeza de ver como isso responde à pergunta ou de usá-lo como responder à pergunta. Estou ciente de todos esses fatos. Descrevo uma maneira específica de especificar idiomas. Você está sugerindo que o Turing está completo? Não parece provável que seja completo para Turing. Um sistema de desigualdades lineares não é completo para Turing, então suspeito / especulo que já o restringi o suficiente para não ser completo para Turing. Além disso, para o método que eu dei para especificar linguagens, não é trivial, pois não é uma expressão regular e nem uma gramática livre de contexto.
DW
-2

Qualquer idioma é aceito por um Push Down Automata, é um CFL. Aqui está uma análise detalhada para determinar se um idioma é CFL ou não. verifique se o idioma é CFL ou não

SiluPanda
fonte
Este não é um algoritmo.
xskxzr 20/04
Não vejo como isso responde à pergunta. Estou ciente de que uma linguagem é livre de contexto se for aceita por um PDA, mas isso não parece ajudar a encontrar um algoritmo do formulário solicitado na pergunta. O artigo geeksforgeeks ao qual você vincula não fornece um algoritmo completo para esse problema; apenas lista casos especiais não exaustivos que são mais fáceis (e não é uma ótima referência, pois algumas de suas declarações são um pouco incompletas / duvidosas).
DW
AFAIK, ainda não existe um algoritmo bem estruturado. (corrija-me se eu estiver errada). O melhor que podemos fazer é verificar os casos.
SiluPanda 22/04
-3

Experimente o software JFLAP se você quiser apenas verificar um CFG. Talvez você possa até pedir aos desenvolvedores do JFLAP que forneçam o código ou algoritmo do software. você pode obter o JFLAP aqui http://www.jflap.org/jflaptmp/ é gratuito, no entanto, requer JDK ou JRE ou algo assim. Ou talvez você possa experimentar outros softwares semelhantes e seus desenvolvedores.

Haseeb Hassan Asif
fonte
1
Não sei se isso responde à pergunta. O JFLAP não possui um recurso que aceite um idioma em notação matemática e informa se é livre de contexto ou não.
Yuval Filmus
TEOREMA 2.20 no livro Sipser Uma linguagem é livre de contexto se e somente se algum autômato de empilhamento a reconhecer. E você pode construir PDA em JFLAP de uma gramática
Haseeb Hassan Asif
Você talvez esteja certo sobre a notação matemática que não pode ser colocada no JFLAP, mas ainda pode colocar todas as regras de uma gramática e ela pode convertê-la em um PDA ou diz que não é um CFG ou algum outro erro
Haseeb Hassan Asif
{umanbncn:nN}
1
Imagino que o JFLAP possa converter uma gramática livre de contexto em um PDA equivalente, mas isso não ajuda em nada aqui.
Yuval Filmus