1
$\begingroup$

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?

$\endgroup$
4
  • $\begingroup$ I am not sure if it is well-known how does a language $L$ correspond to a generating function $F(t)=\sum_i a_i t^i$. Is $a_i$ equal to the number of length $i$ words in $L$? $\endgroup$ May 14, 2014 at 8:05
  • $\begingroup$ @DimaPasechnik,yes,that is what I mean $\endgroup$ May 14, 2014 at 8:06
  • 1
    $\begingroup$ If it is the way I described in my comment then 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. $\endgroup$ May 14, 2014 at 8:08
  • $\begingroup$ (continuing) let $F$ be the GF for a recursively enumerable language 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 $F$, i.e. for a non-Chomsky language. $\endgroup$ May 14, 2014 at 8:20

1 Answer 1

1
$\begingroup$

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.

$\endgroup$
2
  • $\begingroup$ Yes,the generating function $A-F$ may not correspond to c.e.language,since the non-c.e.complement of the set may be productive set,immune set.I have to make some clarification then. $\endgroup$ May 14, 2014 at 9:16
  • $\begingroup$ Seemly It is just possible,not certain. $\endgroup$ May 14, 2014 at 9:31

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.