Formal Grammars and Generating Functions: From Algebraic Structure to Non-Algebraic and Non-Derivable Series

Overview & Synopsis

This paper investigates how the algebraic and analytic properties of ordinary length generating functions constrain the grammatical and computational complexity of formal languages. We review the Chomsky-Schutzenberger representation, DSV translations for unambiguous context-free grammars, and their stack-indexed extensions, distinguishing finite algebraic systems from more general constructions. Examples and a diagonal argument demonstrate that even a rational generating function need not determine a language's grammatical class. Our central computability result establishes that, for a recursively enumerable language, computability of its length-counting sequence is equivalent to decidability of membership. Consequently, if a recursively enumerable language has a D-finite length generating function over Q(z), it is decidable; equivalently, undecidable recursively enumerable languages cannot have D-finite length generating functions. We then examine coefficient growth and singularities through Pringsheim's theorem, the Polya-Carlson dichotomy, Hadamard gaps, and Siegel G-functions. The resulting picture is asymmetric: analytic properties provide useful one-way constraints on language computability, but length enumeration loses too much information to determine grammatical or computational complexity without additional assumptions.