Il est bien connu que le problème d'équivalence est indécidable pour les langages généraux sans contexte. Cependant, toutes les preuves de ce fait que je connais semblent impliquer des grammaires ambiguës sans contexte. Pour cette raison, je voudrais demander si l'on sait si le problème reste indécidable tout en se limitant à des langages sans contexte sans ambiguïté . C'est-à-dire, étant donné deux grammaires sans contexte qui sont a priori accordées pour être sans ambiguïté, est-il décidable qu'elles soient équivalentes ou non?
Je trouve ce problème un peu intriguant, car on sait que l'équivalence est décidable pour les langages déterministes sans contexte, bien que ce résultat soit loin d'être trivial ... D'un autre côté, il pourrait y avoir une raison simple d'indécidabilité que j'ai été surplombant.
Réponses:
Il s'agit actuellement d'un problème ouvert. Comme indiqué à juste titre, si elle est décidable, alors on s'attend à ce que la preuve soit difficile car elle généralise le fameux problème d'équivalence DPDA. D'un autre côté, les arguments classiques pour l'indécidabilité du problème d'universalité CFL utilisent des langages intrinsèquement ambigus, et donc il faut de nouvelles idées pour montrer l'indécidabilité.
Permettez-moi de souligner que le problème d' universalité pour les UCFL est décidable (dans PSPACE), en utilisant des fonctions génératrices [1].
LES RÉFÉRENCES
[1] N. Chomsky et MP Schützenberger, The Algebraic Theory of Context-Free Languages, Computer Programming and Formal Systems, 1963.
la source