# Growth function for non-regular languages

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?

• Which specific classes of languages are you interested in? For arbitrary languages, $\gamma_L(n)$ can be any function whatsoever. – D.W. Jul 13 '20 at 18:10
• 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. – John Jul 14 '20 at 14:23
• 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. – D.W. Jul 14 '20 at 17:37