First,every language in Chomsky hierarchy(or c.e.language) corresponds to a generating function,the set of the functions is GF,now,a question : is every generating function with integral coefficient in GF?


Secondly,of course,if the coefficients are randomly extracted from N,the function may not be in GF.Are all generating functions except the functions with coefficients that can only be constructed by random extraction from N , in GF?


Thirdly,There are many approaches to defining implicitly generating function,such as algebraic equation over some field,differential equation over complex field.Now,is there any list for the approaches?Is there any method or research that is like the study of defining hierarchy of arithmic set and the like or partial computable functions on the generating function.


And the last but not least question :),It seems that there is more subtle correspondence between the generating function and partially computable functions,and more concretely,is there a 1-1 mapping or more subtle mapping between the generating function and the partial computable function?



Approaches to implicitly defining generating function
There certainly are GFs not corresponding to any language in Chomsky hierarchy, as the latter must be recursively enumerable, a property known not to be closed under taking the complement. Indeed, let $F$ be the GF for a recursively enumerable language $L$ with non-recursively enumerable complement, and $A$ the GF for the language of all words. Then $A−F$ is the GF for the complement of $L$, i.e. for a non-Chomsky language.


