A igualdade de idiomas para gramáticas lineares sem contexto é decidível?

Vamos considerar duas gramáticas livres de contexto e e fazer a seguinte pergunta: É , isto é, são as duas gramáticas equivalente? $G_1$ $G_2$ $L(G_1) = L(G_2)$

Em geral, esse problema é indecidível. No entanto, se ambos e lineares esquerda são (ou lineares direita) gramáticas, então o problema é decidível, pois ambas as gramáticas descrever linguagens regulares. $G_1$ $G_2$

Minha pergunta é se o mesmo problema é decidível quando ambas as gramáticas são lineares. Além disso, se alguém puder apontar para a literatura relevante, isso será muito apreciado!

Eu provei como AT neste semestre que é indecidível para gramáticas lineares gerais ( public.asu.edu/~ccolbou/src/555hw3extras16sol.pdf , pergunta 3). É apenas uma redução direta ao problema da igualdade.

A L L_{L G}

$ALL_{LG}$

22716 Ryan

Respostas:

Citando Amiram Yehudai, A Decidibilidade da Equivalência para uma Família de Gramáticas Lineares , Informação e Controle 47, 122-136 (1980) , página 1:

O problema da equivalência para várias famílias de línguas é de grande interesse na teoria das línguas formais. Esse problema é decidível para idiomas regulares (Rabin e Scott, 1959) e indecidível para idiomas livres de contexto (Bar-Hillel et al., 1961). Também é indecidível para a família de linguagens lineares livres de contexto, como segue no Lema 1 de (Baker e Book, 1974). A família de linguagens lineares uniformes é uma subfamília natural e não trivial das linguagens lineares cuja equivalência é decidível.

Isto refere-se a Baker, BS e Book, RV (1974), máquinas multipushdown limitadas por reversão, J. Comput. Sci do sistema 8, 315-332 , que, na prova do Lema 1, apresenta um subconjunto de linguagens lineares livres de contexto, de modo que decidir se um membro do conjunto é igual a equivale a decidir o Problema Pós-Correspondência. $\Sigma^*$

reinierpost
fonte

Excelente resposta! Muito obrigado, isso será muito útil para minha tese de doutorado.

Eu verificaria a prova se fosse você, isso é indireto.

Reinierpost