Es bien sabido que el problema de equivalencia es indecidible para los lenguajes generales sin contexto. Sin embargo, todas las pruebas de este hecho que conozco parecen involucrar algunas gramáticas ambiguas sin contexto. Por esta razón, me gustaría preguntar si se sabe si el problema sigue siendo indecidible mientras se restringe a lenguajes sin contexto inequívocos . Es decir, dadas dos gramáticas libres de contexto que, a priori, se consideran inequívocas, ¿es decidible si son equivalentes o no?
Este problema me parece un poco intrigante, ya que se sabe que la equivalencia es decidible para lenguajes deterministas sin contexto, aunque este resultado está lejos de ser trivial ... Por otro lado, podría haber alguna razón simple para la indecidibilidad de que he sido con vista a.
fuente
Respuestas:
Este es actualmente un problema abierto. Como se señaló correctamente, si es decidible, entonces uno espera que la prueba sea difícil ya que generaliza el famoso problema de equivalencia DPDA. Por otro lado, los argumentos clásicos para la indecidibilidad del problema de universalidad CFL hacen uso de lenguajes intrínsecamente ambiguos y, por lo tanto, uno necesita nuevas ideas para mostrar la indecidibilidad.
Permítanme señalar que el problema de universalidad para las UCFL es decidible (en PSPACE), utilizando funciones generadoras [1].
Referencias
[1] N. Chomsky y MP Schützenberger, La teoría algebraica de lenguajes libres de contexto, programación de computadoras y sistemas formales, 1963.
fuente