On the equality of grammatical families (Q791327)

The grammatical family (GF for short) is a tool devolopment by \textit{A. Cremers} and \textit{S. Ginsburg} [J. Comput. Syst. Sci. 11, 86-117 (1975; Zbl 0328.68071)] as a means allowing to characterize sets of ''similar grammars'' (e.g. regular, linear etc.). Every grammatical family G defines a class of languages L(G). It was open for a long time, whether the equivalence problem for grammatical families (i.e. whether the two GF's define equal classes of languages) is decidable. Using recent results of the authors (''prime families'') it is shown, that every class of languages generated by a GF can be uniquely defined by an expression over a certain algebra. The expression can be constructed effectively. The equivalence problem for grammatical families can be transformed into the problem whether corresponding expressions are ''equivalent''. The equivalence of the expressions is shown to be decidable. The equivalence of GF's therefore also decidable. GF's characterized by expressions of certain canonical form are studied (every GF generating a proper subclass of the context free languages is characterized by such an expression).