Gröbner Bases and the Defining Polynomial of a Context-Free Grammar Generating Function
Alois Panholzer · Journal of automata, languages and combinatorics · 2005
We consider proper algebraic systems as defined in [7] and reprove via Gr{\"{o}}bner bases algorithms that the quasiregular solution of such a system is algebraic. In this context, the effective primary decomposition of a polynomial ideal resp. the effective decomposition of an affine algebraic variety into irreducible components are alternatives to the Kuich-Salomaa elimination algorithm described in [7]. Both here applied decom- positions are based on the construction of a Gr{\"{o}}bner basis of an elimination ideal via Buchberger's algorithm. We reprove then in a constructive way that the generating function of each nonterminal of a context-free grammar is algebraic and also that the generating function of a language, generated by an unambiguous context-free grammar is algebraic (Chomsky-Sch{\"{u}}tzenberger [4]).