For language $L$ over an alphabet $\Sigma$ denote $\gamma_L(n)$ as the number of words of length $n$ in the language $L$. It is known that for regular languages this function represents a sequence with rational generating function (which is equivalent to that $\gamma_L(n)$ is linear-recurrent for sufficiently large coefficients).

However, I couldn't find any information about non-regular languages. And it is not clear how to extend the result, stated above to some other types of languages.

Does anyone know the conditions for some non-regular classes of languages (for example, prefix-closed languages) to have rational geodesic growth function?

  • $\begingroup$ Which specific classes of languages are you interested in? For arbitrary languages, $\gamma_L(n)$ can be any function whatsoever. $\endgroup$
    – D.W.
    Jul 13 '20 at 18:10
  • $\begingroup$ Actually, any information will be useful. However, I am interested in analyzing a prefix-closed (prefix of any word is still in language) non-regular language $L$ such that for every word $w \in L$ there is $v \in \Sigma^*$ such that $wv\in L$ and for every $s\in \Sigma$ the word $wvs$ does not lie in $L$. I don't know how to name this property yet. $\endgroup$
    – John
    Jul 14 '20 at 14:23
  • $\begingroup$ Thanks. It looks like such a language has the form $L=\cup_{w \in L'} \text{prefixes}(w)$ for some language $L'$, where $\text{prefixes}(w)$ is the set of all prefixes of $w$ (including $w$ itself). WLOG we can assume that if $w \in L$ then none of the prefixes of $w$ are in $L$. I'm thinking it might be helpful to edit the question to ask about this class of languages, to make the question more focused. $\endgroup$
    – D.W.
    Jul 14 '20 at 17:37

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.