A equivalência de linguagens livres de contexto inequívocas é decidível?

19

É sabido que o problema da equivalência é indecidível para linguagens gerais livres de contexto. No entanto, todas as provas desse fato que tenho conhecimento parecem envolver algumas gramáticas ambíguas e livres de contexto. Por esse motivo, gostaria de perguntar se é sabido se o problema permanece indecidível enquanto se restringe a linguagens inequívocas sem contexto. Ou seja, dadas duas gramáticas sem contexto que são concedidas a priori como inequívocas, é possível decidir se são equivalentes ou não?

Acho esse problema um pouco intrigante, uma vez que se sabe que a equivalência é decidível para linguagens deterministas livres de contexto, embora esse resultado esteja longe de ser trivial ... Por outro lado, pode haver algum motivo simples de indecidibilidade que eu tenho sido. negligenciar.

fl.formal-languages grammars context-free decidability undecidability Jára Cimrman
fonte
3
A inclusão é indecidível: pdfs.semanticscholar.org/afdb/…
Peter Leupold
4
@PeterLeupold Sim, mas a inclusão também é indecidível para linguagens deterministas livres de contexto, portanto isso é bastante direto (o artigo ao qual você vincula fornece uma prova sem usar esse fato). No entanto, a equivalência parece ser muito mais interessante, uma vez que este é decidível para linguagens livres de contexto determinísticos e undecidable para as línguas gerais livres de contexto ...
Jára Cimrman
3
No entanto, começo a suspeitar que esse problema possa estar aberto: uma prova de decidibilidade é pouco conhecida, já que a das CFLs determinísticas é bastante complicada; por outro lado, a indecidibilidade implicaria indecidibilidade da equivalência das séries algébricas em variáveis ​​não comutativas, que, se eu entendi tudo corretamente, deveria ser um problema em aberto. N
Jára Cimrman

Respostas:

9

Atualmente, este é um problema em aberto. Como corretamente apontado, se for decidível, espera-se que a prova seja difícil, pois generaliza o famoso problema de equivalência do DPDA. Por outro lado, os argumentos clássicos para a indecidibilidade do problema da universalidade da CFL fazem uso de linguagens inerentemente ambíguas e, portanto, são necessárias novas idéias para mostrar a indecidibilidade.

Deixe-me salientar que o problema de universalidade para UCFLs é decidível (no PSPACE), usando funções geradoras [1].

REFERÊNCIAS

[1] N. Chomsky e MP Schützenberger, A teoria algébrica de linguagens livres de contexto, programação de computadores e sistemas formais, 1963.

Lorenzo
fonte
2
Eu acho que você quer dizer línguas inerentemente ambíguas .
Emil Jeřábek apoia Monica
de fato, obrigado @ EmilJeřábek por detectar isso #
Lorenzo