# Number of words of length n for special language

Let $$\Sigma$$ be an alphabet and let $$L$$ be a language over it with the following properties:

1. if $$w\in L$$ then there exists $$v\in \Sigma^*$$ such that $$wv \in L$$ and for every $$s\in \Sigma$$ the word $$wvs$$ does not lie in $$L$$
2. $$wv\in L$$ then $$vw \in L$$
3. It is prefix-closed, i.e. prefix of any word is still in the language.

Note that by the definition, it is not cyclic language. I'm trying to compute its growth function, by that I mean $$\gamma_n:= |\{w\in L \mid |w| = n\}|$$. I know about my specific case that it is not regular and my hypothesis is that function $$\Gamma(x) = \sum_{n=1}^\infty \gamma_nx^n$$ is not rational. However, I couldn't find any information about these functions for non-regular languages. Maybe, there's a formula that connects entropy of language, i.e. $$e(L):= \limsup\limits_{n\to\infty} \frac{\log\gamma_n}{n}$$ and the $$\Gamma$$ function. Or for such a language there's a way to describe its growth throughout the growth of the language $$\operatorname{End}(L) = \{ w\in L \mid \forall s\in \Sigma \,ws \text{ is not in } L \}$$.

• Do you have a specific language in mind? – Yuval Filmus Jul 22 at 16:40
• Assume that the language contains a word with more than $0$ letters: $\omega \in L, \omega = \alpha x , |\alpha |\geq 0, x\in\Sigma$. By property (3): $\alpha \in L$. But by property (1) $\alpha x \notin L$ for all $x\in \Sigma$. Hence we have a contradiction. Your languages only contain the empty word $\varepsilon$ or are completely empty. – plshelp Jul 22 at 17:18
• No, you're mistaken. You represent $w = \alpha x$, where $x\in \Sigma$. The (1) states only that there's a continuation for $\alpha$ that cannot be continued to a word in $L$ that itself cannot be continued. – John Jul 22 at 19:34
• There are multiple such languages. You need to be more specific. – Dmitry Jul 23 at 21:17