Consideremos dos gramáticas libres de contexto y y la siguiente pregunta: ¿Es , es decir, son las dos gramáticas equivalentes?
En general, este problema es indecidible. Sin embargo, si y son gramáticas lineales a la izquierda (o lineales a la derecha), entonces el problema es decidible, porque ambas gramáticas describen lenguajes regulares.
Mi pregunta es si el mismo problema es decidible cuando ambas gramáticas son lineales. Además, si alguien puede señalar literatura relevante, ¡eso será muy apreciado!
Respuestas:
Citando de Amiram Yehudai, The Decidability of Equivalence for a Family of Linear Grammars , Information and Control 47, 122-136 (1980) , página 1:
Esto se refiere a Baker, BS y Book, RV (1974), máquinas multipushdown accionadas por inversión, J. Comput. System Sci. 8, 315-332 , que, en la prueba de ese Lema 1, presenta un subconjunto de lenguajes lineales libres de contexto de tal manera que decidir si un miembro del conjunto es igual a es equivalente a decidir el Problema posterior a la correspondencia.Σ∗
fuente