¿Es la igualdad de lenguaje para gramáticas lineales libres de contexto decidible?

19

Consideremos dos gramáticas libres de contexto y y la siguiente pregunta: ¿Es , es decir, son las dos gramáticas equivalentes?G1G2L(G1)=L(G2)

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.G1G2

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!


fuente
2
Este semestre que es indecidible para las gramáticas lineales generales ( public.asu.edu/~ccolbou/src/555hw3extras16sol.pdf , Pregunta 3). Es solo una reducción directa al problema de la igualdad. ALLLG
Ryan

Respuestas:

12

Citando de Amiram Yehudai, The Decidability of Equivalence for a Family of Linear Grammars , Information and Control 47, 122-136 (1980) , página 1:

El problema de equivalencia para varias familias de lenguas es de gran interés en la teoría de las lenguas formales. Este problema es decidible para los idiomas regulares (Rabin y Scott, 1959) e indecidible para los idiomas libres de contexto (Bar-Hillel et al., 1961). También es indecidible para la familia de lenguajes lineales libres de contexto, como se deduce de Lemma 1 en (Baker y Book, 1974). La familia de lenguajes lineales uniformes es una subfamilia natural y no trivial de los lenguajes lineales para los cuales la equivalencia es decidible.

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.Σ

reinierpost
fuente
Excelente respuesta! Muchas gracias, esto será muy útil para mi tesis doctoral.
Verificaría la prueba si fuera usted, esto es bastante indirecto.
reinierpost