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?

Improve this question
$\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$
    – Dima Pasechnik
    Commented May 14, 2014 at 8:05
  • $\begingroup$ @DimaPasechnik,yes,that is what I mean $\endgroup$
    – XL _At_Here_There
    Commented 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$
    – Dima Pasechnik
    Commented 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$
    – Dima Pasechnik
    Commented May 14, 2014 at 8:20

1 Answer 1

Reset to default
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.

Improve this answer
$\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$
    – XL _At_Here_There
    Commented May 14, 2014 at 9:16
  • $\begingroup$ Seemly It is just possible,not certain. $\endgroup$
    – XL _At_Here_There
    Commented May 14, 2014 at 9:31

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .