L'égalité linguistique pour les grammaires linéaires sans contexte est-elle décidable?

Considérons deux grammaires contexte et et la question suivante: , c'est-à-dire, les deux grammaires sont-elles équivalentes? $G_1$ $G_2$ $L(G_1) = L(G_2)$

En général, ce problème est indécidable. Cependant, si et sont des gauche (ou à droite), le problème est décidable, car les deux grammaires décrivent des langues normales. $G_1$ $G_2$

Ma question est de savoir si le même problème est décidable ou non lorsque les deux grammaires sont linéaires. De plus, si quelqu'un peut pointer vers la littérature pertinente, cela sera très apprécié!

J'ai prouvé en tant qu'AT ce semestre que

est indécidable pour les grammaires linéaires générales ( public.asu.edu/~ccolbou/src/555hw3extras16sol.pdf , question 3). Ce n'est qu'une simple réduction du problème de l'égalité.

A L L_{L G}

$ALL_{LG}$

Ryan

Réponses:

Citant Amiram Yehudai, The Decidability of Equivalence for a Family of Linear Grammars , Information and Control 47, 122-136 (1980) , page 1:

Le problème d'équivalence pour diverses familles de langues présente un grand intérêt pour la théorie des langues formelles. Ce problème est décidable pour les langues régulières (Rabin et Scott, 1959) et indécidable pour les langues sans contexte (Bar-Hillel et al., 1961). Il est également indécidable pour la famille des langages linéaires sans contexte, comme suit du lemme 1 dans (Baker et Book, 1974). La famille des langages linéaires uniformes est une sous-famille naturelle et non triviale des langages linéaires pour lesquels l'équivalence est décidable.

$\Sigma^*$

reinierpost
la source

Excellente réponse! Merci beaucoup, cela sera très utile pour ma thèse de doctorat.

Je vérifierais la preuve si j'étais toi, c'est plutôt indirect.

reinierpost