¿Es decidible la equivalencia de lenguajes libres de contexto inequívocos?

19

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.

Jára Cimrman
fuente
3
La inclusión es indecidible: pdfs.semanticscholar.org/afdb/…
Peter Leupold
44
@PeterLeupold Sí, pero la inclusión también es indecidible para los lenguajes deterministas libres de contexto, por lo que esto es bastante sencillo (el artículo al que se vincula solo proporciona una prueba sin utilizar este hecho). Sin embargo, la equivalencia parece ser mucho más interesante, ya que esto es decidible para lenguajes deterministas sin contexto e indecidible para lenguajes generales sin contexto ...
Jára Cimrman
3
Sin embargo, empiezo a sospechar que este problema podría estar abierto: apenas se conoce una prueba de capacidad de decisión, ya que la de las CFL deterministas es bastante complicada; Por otro lado, la indecidibilidad implicaría la indecidibilidad de la equivalencia de las series algebraicas en variables no conmutativas, lo que, si entendí todo correctamente, debería ser un problema abierto. norte
Jára Cimrman

Respuestas:

9

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.

Lorenzo
fuente
2
Creo que te refieres a lenguajes intrínsecamente ambiguos .
Emil Jeřábek apoya a Monica el
de hecho, gracias a @ EmilJeřábek por ver esto
Lorenzo