Finite generation of ambiguity in context-free languages (Q1117043)

Let us recall that, for any pair \((L_ 1,L_ 2)\) of sub-languages of a context-free language L, the intersection \(L_ 1\cap L_ 2\) is said to be finitely presented if and only if there exist finitely many intersection components \(Z_ k\), algebraically generated sub-languages both of \(L_ 1\) and \(L_ 2\), partitioning \(L_ 1\cap L_ 2.\) First of all, this paper gives a categorical presentation for context- free languages generation: it permits particularly to model the ambiguity of a context-free language as a congruence on the category of derivations. Within this categorical model, a pair of sufficient conditions is presented so that, when a context-free grammar G is given, the intersection of a certain class of sub-languages of L(G) is finitely presented. When these conditions hold for a context-free grammar, the ambiguity of L(G) is shown to be finitely generated. The author establishes also that the conditions he gives cannot be necessary, because they are proved to be equivalent to undecidable problems for context-free grammars.